/*
 * Copyright (C) 2011 by Zhang Li <RichSelian at gmail.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the project nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
#ifndef CMACRO_LIB_H_INCLUDED
#define CMACRO_LIB_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>

#ifdef __GNUC__
#define __unused __attribute__((unused))
#else
#define __unused
#endif

#if defined(__GNUC__) || defined(__INTEL_COMPILER)
// gcc/clang/icc
#define __cm_thread_safe __thread
#elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
// vc/bc/dmc
#define __cm_thread_safe __declspec(thread)
#else
#warning "your compiler do not support TLS variants to make cmacro threaded-safe."
#define __cm_thread_safe
#endif

/* exception */
/******************************************************************************/
#define cm_try_begin()                                                      \
    do {                                                                    \
        extern jmp_buf __cm_thread_safe __cm_jmp_buf[128];                  \
        extern size_t __cm_thread_safe __cm_jmp_pos;                        \
        int __jmp_ret;                                                      \
        if((__jmp_ret = setjmp(__cm_jmp_buf[__cm_jmp_pos++])) == 0) {

#define cm_try_catch(exception)                                             \
        } else if(__jmp_ret == (exception)) {                               \
            extern size_t __cm_thread_safe __cm_jmp_pos;                    \
            __cm_jmp_pos--;                                                 \

#define cm_try_end()                                                        \
        } else {                                                            \
            extern size_t __cm_thread_safe __cm_jmp_pos;                    \
            __cm_jmp_pos--;                                                 \
            cm_try_throw(__jmp_ret);                                        \
        }                                                                   \
    } while(0)

#define cm_try_throw(exception)                                             \
    do {                                                                    \
        extern jmp_buf __cm_thread_safe __cm_jmp_buf[128];                  \
        extern size_t __cm_thread_safe __cm_jmp_pos;                        \
        if(__cm_jmp_pos > 0)                                                \
        {                                                                   \
            longjmp(__cm_jmp_buf[__cm_jmp_pos - 1], (exception));           \
        }                                                                   \
        else                                                                \
        {                                                                   \
            fprintf(stderr, "unhandled exception %d at file %s, line %d\n", (exception), __FILE__, __LINE__); \
            exit(EXIT_FAILURE);                                             \
        }                                                                   \
    } while(0)

/* basic operation */
/******************************************************************************/
#define cm_basic_swap(type, x1, x2)                                         \
    do {                                                                    \
        type* __p1 = (type*)x1;                                             \
        type* __p2 = (type*)x2;                                             \
        type __tmp;                                                         \
        __tmp = *__p1, *__p1 = *__p2, *__p2 = __tmp;                        \
    } while(0)

#define cm_basic_cmp_gt(x, y) ((x) - (y))
#define cm_basic_cmp_lt(x, y) ((y) - (x))

#define cm_basic_cmp cm_basic_cmp_gt

#define cm_alloc_error_id   (-1)
#define cm_malloc(x)        __cm_malloc(x)
#define cm_calloc(x, y)     __cm_calloc(x, y)
#define cm_realloc(x, y)    __cm_realloc(x, y)
#define cm_free(x)          __cm_free(x)

static __unused void* __cm_malloc(size_t size)
{
    void* ptr = malloc(size);
    if(!ptr)
        cm_try_throw(-1);
    return ptr;
}
static __unused void* __cm_calloc(size_t nmemb, size_t size)
{
    void* ptr = calloc(nmemb, size);
    if(!ptr)
        cm_try_throw(-1);
    return ptr;
}
static __unused void* __cm_realloc(void* ptr, size_t size)
{
    ptr = realloc(ptr, size);
    if(!ptr)
        cm_try_throw(-1);
    return ptr;
}
static __unused void __cm_free(void* ptr)
{
    free(ptr);
    return;
}

/* array numeric operation */
/******************************************************************************/
#define cm_array_numeric_max(array, type, size, cmp, result_index)          \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __i;                                                         \
        size_t __result_index;                                              \
        \
        for(__result_index = 0, __i = 1; __i < __size; __i++)               \
        {                                                                   \
            if(cmp(__array[__i], __array[__result_index]) > 0)              \
            {                                                               \
                __result_index = __i;                                       \
            }                                                               \
        }                                                                   \
        (result_index) = __result_index;                                    \
    } while(0)

#define cm_array_numeric_min(array, type, size, cmp, result_index)          \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __i;                                                         \
        size_t __result_index;                                              \
        \
        for(__result_index = 0, __i = 1; __i < __size; __i++)               \
        {                                                                   \
            if(cmp(__array[__i], __array[__result_index]) < 0)              \
            {                                                               \
                __result_index = __i;                                       \
            }                                                               \
        }                                                                   \
        (result_index) = __result_index;                                    \
    } while(0)

#define cm_array_numeric_sum(array, type, size, result)                     \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __i;                                                         \
        type __result = 0;                                                  \
        \
        for(__i = 0; __i < __size; __i++)                                   \
        {                                                                   \
            __result += __array[__i];                                       \
        }                                                                   \
        (result) = __result;                                                \
    } while(0)

#define cm_array_numeric_average(array, type, size, result)                 \
    do {                                                                    \
        type __avr_sum;                                                     \
        size_t __avr_size = (size);                                         \
        \
        cm_array_numeric_sum(type, array, __avr_size, __avr_sum);           \
        (result) = __avr_sum / __avr_size;                                  \
    } while(0)

/* array sorting operation */
/******************************************************************************/
/* insertion sort */
#define cm_array_insertion_sort(array, type, size, cmp)                     \
    do {                                                                    \
        type* __isort_array = (array);                                      \
        size_t __isort_size = (size);                                       \
        size_t __i;                                                         \
        size_t __j;                                                         \
        type __temp_data;                                                   \
        \
        for(__i = 1; __i < __isort_size; __i++)                             \
        {                                                                   \
            __temp_data = __isort_array[__i];                               \
            __j = __i;                                                      \
            while(__j > 0 && cmp(__temp_data, __isort_array[__j - 1]) < 0)  \
            {                                                               \
                __isort_array[__j] = __isort_array[__j - 1];                \
                __j -= 1;                                                   \
            }                                                               \
            __isort_array[__j] = __temp_data;                               \
        }                                                                   \
    } while(0)

/* comb sort */
#define cm_array_comb_sort(array, type, size, cmp)                          \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __i;                                                         \
        size_t __step = __size / 3;                                         \
        \
        while(__step > 16)                                                  \
        {                                                                   \
            for(__i = 0; __i + __step < __size; __i++)                      \
            {                                                               \
                if(cmp(__array[__i], __array[__i + __step]) > 0)            \
                {                                                           \
                    cm_basic_swap(type, __array + __i, __array + __i + __step);\
                }                                                           \
            }                                                               \
            __step = __step * 3 / 4;                                        \
        }                                                                   \
        cm_array_insertion_sort(array, type, size, cmp);                    \
    } while(0)

/* heap sort */
#define cm_array_heap_sort(array, type, size, cmp)                          \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __current;                                                   \
        size_t __next;                                                      \
        size_t __top = __size / 2;                                          \
        type __tempdata;                                                    \
        \
        while(__size > 0)                                                   \
        {                                                                   \
            if(__top) __top -= 1; else cm_basic_swap(type, &__array[--__size], &__array[0]); \
            \
            __tempdata = __array[__top];                                    \
            __current = __top;                                              \
            while(1)                                                        \
            {                                                               \
                __next = __current * 2 + 1;                                 \
                if(__next + 1 < __size && cmp(__array[__next], __array[__next + 1]) < 0) \
                {                                                           \
                    __next += 1;                                            \
                }                                                           \
                if(__next < __size)                                         \
                {                                                           \
                    __array[__current] = __array[__next];                   \
                    __current = __next;                                     \
                } else break;                                               \
            }                                                               \
            \
            while(1)                                                        \
            {                                                               \
                __next = (__current - 1) / 2;                               \
                if(__next >= __top && cmp(__array[__next], __tempdata) < 0) \
                {                                                           \
                    __array[__current] = __array[__next];                   \
                    __current = __next;                                     \
                } else break;                                               \
            }                                                               \
            __array[__current] = __tempdata;                                \
        }                                                                   \
    } while(0)

/* merge sort */
#define cm_array_merge_sort(array, type, size, cmp)                         \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        int __step_width;                                                   \
        int __i;                                                            \
        int __ins;                                                          \
        int __l;                                                            \
        int __m;                                                            \
        int __r;                                                            \
        int __scanner_l;                                                    \
        int __scanner_r;                                                    \
        type* __temp_array;                                                 \
        \
        __temp_array = (type*)__cm_malloc(sizeof(type) * __size);           \
        for(__step_width = 16; __step_width < __size * 2; __step_width *= 2)\
        {                                                                   \
            for(__i = 0; __i < __size; __i += __step_width)                 \
            {                                                               \
                __l = __i;                                                  \
                __m = __i + __step_width / 2;                               \
                __r = __i + __step_width;                                   \
                \
                __m = __m < __size ? __m : __size;                          \
                __r = __r < __size ? __r : __size;                          \
                \
                if(__r - __l <= 16)                                         \
                {                                                           \
                    cm_array_insertion_sort(__array + __l, type, __r - __l, cmp); \
                    continue;                                               \
                }                                                           \
                \
                __scanner_l = __l;                                          \
                __scanner_r = __m;                                          \
                __ins = 0;                                                  \
                while(__scanner_l < __m && __scanner_r < __r)               \
                {                                                           \
                    if(cmp(__array[__scanner_l], __array[__scanner_r]) <= 0)\
                    {                                                       \
                        __temp_array[__ins++] = __array[__scanner_l++];     \
                    } else {                                                \
                        __temp_array[__ins++] = __array[__scanner_r++];     \
                    }                                                       \
                }                                                           \
                while(__scanner_l < __m) __temp_array[__ins++] = __array[__scanner_l++]; \
                while(__scanner_r < __r) __temp_array[__ins++] = __array[__scanner_r++]; \
                memcpy(__array + __l, __temp_array, (__r - __l) * sizeof(type)); \
            }                                                               \
        }                                                                   \
        __cm_free(__temp_array);                                            \
    } while(0)

/* quick sort */
#define cm_array_quick_sort(array, type, size, cmp)                         \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __stack[sizeof(size_t) * 128];                               \
        size_t* __sp = __stack;                                             \
        \
        *(__sp++) = 0;                                                      \
        *(__sp++) = __size - 1;                                             \
        \
        while(__sp != __stack)                                              \
        {                                                                   \
            size_t __hi = *(--__sp);                                        \
            size_t __lo = *(--__sp);                                        \
            size_t __l = __lo;                                              \
            size_t __r = __hi;                                              \
            size_t __m = (__hi + __lo) / 2;                                 \
            type __pivot;                                                   \
            \
            if(__hi - __lo <= 16) continue;                                 \
            if(cmp(__array[__l], __array[__r]) > 0) cm_basic_swap(type, __array + __l, __array + __r); \
            if(cmp(__array[__l], __array[__m]) > 0) cm_basic_swap(type, __array + __l, __array + __m); \
            if(cmp(__array[__m], __array[__r]) > 0) cm_basic_swap(type, __array + __m, __array + __r); \
            \
            __pivot = __array[__m];                                         \
            while(__l <= __r)                                               \
            {                                                               \
                while(cmp(__array[__l], __pivot) < 0) __l++;                \
                while(cmp(__array[__r], __pivot) > 0) __r--;                \
                if(__l <= __r)                                              \
                {                                                           \
                    cm_basic_swap(type, __array + __l, __array + __r);      \
                    __l++;                                                  \
                    __r--;                                                  \
                }                                                           \
            }                                                               \
            if((__r - __lo) > (__hi - __l))                                 \
            {                                                               \
                *(__sp++) = __lo, *(__sp++) = __r;                          \
                *(__sp++) = __l, *(__sp++) = __hi;                          \
            } else {                                                        \
                *(__sp++) = __l, *(__sp++) = __hi;                          \
                *(__sp++) = __lo, *(__sp++) = __r;                          \
            }                                                               \
        }                                                                   \
        cm_array_insertion_sort(__array, int, __size, cmp);                 \
    } while(0)

/* counting sort */
#define cm_array_counting_sort(array, type, size, range_lo, range_hi, counting_hash) \
    do {                                                                    \
        type* __array = (type*)(array);                                     \
        size_t __size = (size);                                             \
        size_t __range_lo = (range_lo);                                     \
        size_t __range_hi = (range_hi);                                     \
        \
        type* __result_array = __cm_malloc(sizeof(type) * __size);          \
        size_t* __counting_array = __cm_malloc(sizeof(size_t) * (__range_hi - __range_lo)); \
        size_t __i;                                                         \
        size_t __count = 0;                                                 \
        \
        memset(__counting_array, 0, sizeof(size_t) * (__range_hi - __range_lo)); \
        for(__i = 0; __i < __size; __i++)                                   \
        {                                                                   \
            __counting_array[counting_hash(__array[__i]) - range_lo] += 1;  \
        }                                                                   \
        for(__i = __range_lo; __i < __range_hi; __i++)                      \
        {                                                                   \
            __count += __counting_array[__i];                               \
            __counting_array[__i] = __count - __counting_array[__i];        \
        }                                                                   \
        for(__i = 0; __i < __size; __i++)                                   \
        {                                                                   \
            __result_array[__counting_array[counting_hash(__array[__i]) - __range_lo]++] = __array[__i]; \
        }                                                                   \
        memcpy(__array, __result_array, sizeof(type) * __size);             \
        __cm_free(__result_array);                                          \
        __cm_free(__counting_array);                                        \
    } while(0)

#define cm_counting_hash_byte0(x)   ((x) & 0xff)
#define cm_counting_hash_byte1(x)   (((x) >> 8) & 0xff)
#define cm_counting_hash_byte2(x)   (((x) >> 16) & 0xff)
#define cm_counting_hash_byte3(x)   (((x) >> 24) & 0xff)
#define cm_counting_hash_byte4(x)   (((x) >> 32) & 0xff)
#define cm_counting_hash_byte5(x)   (((x) >> 40) & 0xff)
#define cm_counting_hash_byte6(x)   (((x) >> 48) & 0xff)
#define cm_counting_hash_byte7(x)   (((x) >> 56) & 0xff)

#define cm_counting_hash_word0(x)   ((x) & 0xffff)
#define cm_counting_hash_word1(x)   (((x) >> 16) & 0xffff)
#define cm_counting_hash_word2(x)   (((x) >> 32) & 0xffff)
#define cm_counting_hash_word3(x)   (((x) >> 48) & 0xffff)

/* partial quick sort */
#define cm_array_partial_quick_sort(array, type, size, partial_lo, partial_hi, cmp) \
    do {                                                                    \
        type* __array = (type*)(array);                                     \
        size_t __size = (size);                                             \
        size_t __partial_lo = (partial_lo);                                 \
        size_t __partial_hi = (partial_hi);                                 \
        size_t __stack[sizeof(size_t) * 128];                               \
        size_t* __sp = __stack;                                             \
        \
        *(__sp++) = 0;                                                      \
        *(__sp++) = __size - 1;                                             \
        \
        while(__sp != __stack)                                              \
        {                                                                   \
            size_t __hi = *(--__sp);                                        \
            size_t __lo = *(--__sp);                                        \
            size_t __l = __lo;                                              \
            size_t __r = __hi;                                              \
            size_t __m = (__hi + __lo) / 2;                                 \
            type __pivot;                                                   \
            \
            if(__lo >= __partial_hi || __hi < __partial_lo) continue;       \
            if(__hi - __lo < 32)                                            \
            {                                                               \
                cm_array_insertion_sort(__array + __lo, int, __hi - __lo + 1, cmp); \
                continue;                                                   \
            }                                                               \
            if(cmp(__array[__l], __array[__r]) > 0) cm_basic_swap(type, __array + __l, __array + __r); \
            if(cmp(__array[__l], __array[__m]) > 0) cm_basic_swap(type, __array + __l, __array + __m); \
            if(cmp(__array[__m], __array[__r]) > 0) cm_basic_swap(type, __array + __m, __array + __r); \
            \
            __pivot = __array[__m];                                         \
            while(__l <= __r)                                               \
            {                                                               \
                while(cmp(__array[__l], __pivot) < 0) __l++;                \
                while(cmp(__pivot, __array[__r]) < 0) __r--;                \
                if(__l <= __r)                                              \
                {                                                           \
                    cm_basic_swap(type, __array + __l, __array + __r);      \
                    __l++;                                                  \
                    __r--;                                                  \
                }                                                           \
            }                                                               \
            if((__r - __lo) > (__hi - __l))                                 \
            {                                                               \
                *(__sp++) = __lo, *(__sp++) = __r;                          \
                *(__sp++) = __l, *(__sp++) = __hi;                          \
            } else {                                                        \
                *(__sp++) = __l, *(__sp++) = __hi;                          \
                *(__sp++) = __lo, *(__sp++) = __r;                          \
            }                                                               \
        }                                                                   \
    } while(0)

/* array permuting operation */
/******************************************************************************/
#define cm_array_reverse(array, type, size)                                 \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __pos_l = 0;                                                 \
        size_t __pos_r = __size - 1;                                        \
        \
        while(__pos_l < __pos_r)                                            \
        {                                                                   \
            cm_basic_swap(type, __array + __pos_l, __array + __pos_r);      \
            __pos_l++;                                                      \
            __pos_r--;                                                      \
        }                                                                   \
    } while(0)

#define cm_array_shuffle(array, type, size)                                 \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        size_t __i;                                                         \
        size_t __rand_index;                                                \
        \
        for(__i = 1; __i < __size; __i++)                                   \
        {                                                                   \
            __rand_index = (rand() % (__i + 1));                            \
            cm_basic_swap(type, __array + __i, __array + __rand_index);     \
        }                                                                   \
    } while(0)

#define cm_array_permute_next(array, type, size, cmp, is_ended)             \
    do {                                                                    \
        type* __array = (array);                                            \
        size_t __size = (size);                                             \
        int __i = __size - 2;                                               \
        int __j = __size - 1;                                               \
        \
        while(__i >= 0 && cmp(__array[__i], __array[__i + 1]) >= 0)         \
        {                                                                   \
            __i--;                                                          \
        }                                                                   \
        if(!((is_ended) = (__i < 0)))                                       \
        {                                                                   \
            while(cmp(__array[__i], __array[__j]) >= 0)                     \
            {                                                               \
                __j--;                                                      \
            }                                                               \
            \
            cm_basic_swap(type, __array + __i, __array + __j);              \
        }                                                                   \
        \
        for(__i = __i + 1, __j = __size - 1; __i < __j; __i++, __j--)       \
        {                                                                   \
            cm_basic_swap(type, __array + __i, __array + __j);              \
        }                                                                   \
    } while(0)

#define cm_array_permute_prev(array, type, size, cmp, is_ended)             \
    do {                                                                    \
        cm_array_permute_next(type, array, size, 0 - cmp, is_ended);        \
    } while(0)

/* vector */
/******************************************************************************/
typedef struct __cm_vector_struct
{
    size_t __capacity;
    size_t __size;
    void* __data;
} __cm_vector, *__cm_vector_ptr;

#define cm_vector_type  __cm_vector_ptr

#define cm_vector_init(vector)                                              \
    do {                                                                    \
        __cm_vector* __vector;                                              \
        \
        __vector = (__cm_vector*)__cm_malloc(sizeof(__cm_vector));          \
        __vector->__capacity = 0;                                           \
        __vector->__size = 0;                                               \
        __vector->__data = NULL;                                            \
        (vector) = __vector;                                                \
    } while(0)

#define cm_vector_destroy(vector)                                           \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        \
        __cm_free(__vector->__data);                                        \
        __cm_free(__vector);                                                \
    } while(0)

#define cm_vector_size(vector) ((vector)->__size)

#define cm_vector_clear(vector)                                             \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        __vector->__size = 0;                                               \
        __vector->__capacity = 0;                                           \
        __vector->__data = __cm_realloc(__vector->__data, 0);               \
    } while(0)

#define cm_vector_resize(vector, size, type)                                \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        size_t __size = (size);                                             \
        __vector->__capacity = __size;                                      \
        __vector->__size = __size;                                          \
        __vector->__data = realloc(__vector->__data, __size * sizeof(type));\
    } while(0)

#define cm_vector_insert_range(vector, pos, len, type, data)                \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        size_t __pos = (pos);                                               \
        size_t __len = (len);                                               \
        type* __data = (data);                                              \
        type* __mov_src;                                                    \
        type* __mov_dst;                                                    \
        int __ins;                                                          \
        \
        if(__vector->__size + __len > (vector)->__capacity)                 \
        {                                                                   \
            __vector->__capacity = (__vector->__size + __len) * 2 + 1;      \
            __vector->__data = __cm_realloc(__vector->__data, __vector->__capacity * sizeof(type)); \
        }                                                                   \
        \
        __mov_dst = (type*)__vector->__data + __pos + __len;                \
        __mov_src = (type*)__vector->__data + __pos;                        \
        memmove(dst, src, sizeof(type) * (__vector->__size - __pos));       \
        \
        for(__ins = 0; __ins < __len; __ins += 1)                           \
        {                                                                   \
            *((type*)__vector->__data + __pos + __ins) = __data[__ins];     \
        }                                                                   \
        __vector->__size += __len;                                          \
    } while(0)

#define cm_vector_remove_range(vector, pos, len, type)                      \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        size_t __pos = (pos);                                               \
        size_t __len = (len);                                               \
        type* __mov_src;                                                    \
        type* __mov_dst;                                                    \
        \
        if(__vector->__size - __len < __vector->__capacity / 3)             \
        {                                                                   \
            __vector->__capacity = (__vector->__size - __len) * 2 + 1;      \
            __vector->__data = __cm_realloc(__vector->__data, __vector->__capacity * sizeof(type)); \
        }                                                                   \
        \
        __mov_dst = (type*)__vector->__data + __pos;                        \
        __mov_src = (type*)__vector->__data + __pos + __len;                \
        memmove(__mov_dst, __mov_src, sizeof(type) * (__vector->__size - __pos - __len)); \
        \
        __vector->__size -= __len;                                          \
    } while(0)

#define cm_vector_insert(vector, pos, type, data)                           \
    do {                                                                    \
        __cm_vector* __vector = (vector);                                   \
        size_t __pos = (pos);                                               \
        type __data = (data);                                               \
        type* __mov_src;                                                    \
        type* __mov_dst;                                                    \
        \
        if(__vector->__size + 1 > __vector->__capacity)                     \
        {                                                                   \
            __vector->__capacity = (__vector->__size + 1) * 2 + 1;          \
            __vector->__data = __cm_realloc(__vector->__data, __vector->__capacity * sizeof(type)); \
        }                                                                   \
        \
        __mov_dst = (type*)__vector->__data + __pos + 1;                    \
        __mov_src = (type*)__vector->__data + __pos;                        \
        memmove(__mov_dst, __mov_src, sizeof(type) * (__vector->__size - __pos)); \
        \
        *((type*)__vector->__data + __pos) = __data;                        \
        __vector->__size += 1;                                              \
    } while(0)

#define cm_vector_remove(vector, pos, type)                                 \
    cm_vector_remove_range(vector, pos, 1, type)

#define cm_vector_append(vector, type, data)                                \
    do {                                                                    \
        __cm_vector* __va_vector = (vector);                                \
        cm_vector_insert(__va_vector, cm_vector_size(__va_vector), type, data); \
    } while(0)

static __unused void* __cm_vector_lastdata_ptr_sub(__cm_vector* vector, size_t itemsize)
{
    return (char*)vector->__data + (vector->__size - 1) * itemsize;
}
#define cm_vector_lastdata(vector, type)        (*(type*)__cm_vector_lastdata_ptr_sub(vector, sizeof(type)))
#define cm_vector_lastdata_ptr(vector, type)    ((type*)__cm_vector_lastdata_ptr_sub(vector, sizeof(type)))

#define cm_vector_remove_last(vector, type)                                 \
    do {                                                                    \
        __cm_vector* __vrl_vector = (vector);                               \
        cm_vector_remove(__vrl_vector, cm_vector_size(__vrl_vector) - 1, type); \
    } while(0)

#define cm_vector_array_ptr(vector, type)                                   \
    ((type*)(vector)->__data)

#define cm_vector_data_ptr_at(vector, pos, type)                            \
    ((type*)(vector)->__data + (pos))

#define cm_vector_data_at(vector, pos, type)                                \
    (*((type*)(vector)->__data + (pos)))

/* linked list */
/******************************************************************************/
typedef struct __cm_list_node_struct
{
    struct __cm_list_node_struct* __prev;
    struct __cm_list_node_struct* __next;
} __cm_list_node, *__cm_list_node_ptr;

typedef struct __cm_list_struct
{
    struct __cm_list_node_struct* __head;
    size_t __size;
} __cm_list, *__cm_list_ptr;

#define cm_list_type        __cm_list_ptr
#define cm_list_node_type   __cm_list_node_ptr

#define cm_list_init(list)                                                  \
    do {                                                                    \
        __cm_list* __list;                                                  \
        \
        __list = (__cm_list*)__cm_malloc(sizeof(__cm_list));                \
        __list->__head = (__cm_list_node*)__cm_malloc(sizeof(__cm_list_node)); \
        \
        __list->__head->__next = __list->__head;                            \
        __list->__head->__prev = __list->__head;                            \
        __list->__size = 0;                                                 \
        (list) = __list;                                                    \
    } while(0)

#define cm_list_destroy(list)                                               \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        __cm_list_node* __node;                                             \
        \
        while(__list->__head->__next != __list->__head)                     \
        {                                                                   \
            __node = __list->__head->__next;                                \
            __node->__next->__prev = __node->__prev;                        \
            __node->__prev->__next = __node->__next;                        \
            __cm_free(__node);                                              \
        }                                                                   \
        __cm_free(__list->__head);                                          \
        __cm_free(__list);                                                  \
    } while(0)

#define cm_list_size(list) ((list)->__size)

#define cm_list_insert(list, pos, type, data)                               \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        type __data = (data);                                               \
        __cm_list_node* __new_node;                                         \
        __cm_list_node* __insert_pos = (pos);                               \
        \
        __new_node = (__cm_list_node*)__cm_malloc(sizeof(__cm_list_node) + sizeof(type)); \
        *(type*)(__new_node + 1) = __data;                                  \
        if(__insert_pos)                                                    \
        {                                                                   \
            __new_node->__next = __insert_pos;                              \
            __new_node->__prev = __insert_pos->__prev;                      \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __new_node->__next = __list->__head;                            \
            __new_node->__prev = __list->__head->__prev;                    \
        }                                                                   \
        __new_node->__next->__prev = __new_node;                            \
        __new_node->__prev->__next = __new_node;                            \
        __list->__size += 1;                                                \
    } while(0)

#define cm_list_remove(list, pos)                                           \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        __cm_list_node* __remove_node = (pos);                              \
        \
        __remove_node->__next->__prev = __remove_node->__prev;              \
        __remove_node->__prev->__next = __remove_node->__next;              \
        __cm_free(__remove_node);                                           \
        __list->__size -= 1;                                                \
    } while(0)

#define cm_list_append(list, type, data) cm_list_insert(list, NULL, type, data)

#define cm_list_insert_node_splice(list, pos, node, from_list)              \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        __cm_list* __from_list = (from_list);                               \
        __cm_list_node* __splice_node = (node);                             \
        __cm_list_node* __insert_pos = (pos);                               \
        \
        __splice_node->__next->__prev = __splice_node->__prev;              \
        __splice_node->__prev->__next = __splice_node->__next;              \
        \
        if(__insert_pos)                                                    \
        {                                                                   \
            __splice_node->__next = __insert_pos;                           \
            __splice_node->__prev = __insert_pos->__prev;                   \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __splice_node->__next = __list->__head;                         \
            __splice_node->__prev = __list->__head->__prev;                 \
        }                                                                   \
        __splice_node->__next->__prev = __splice_node;                      \
        __splice_node->__prev->__next = __splice_node;                      \
        if(__from_list != __list)                                           \
        {                                                                   \
            __from_list->__size -= 1;                                       \
            __list->__size += 1;                                            \
        }                                                                   \
    } while(0)

#define cm_list_concatenate(list1, list2)                                   \
    do {                                                                    \
        __cm_list* __list1 = (list1);                                       \
        __cm_list* __list2 = (list2);                                       \
        __cm_list_node* __list2_head = __list2->__head->__next;             \
        __cm_list_node* __list2_tail = __list2->__head->__prev;             \
        \
        if(__list2->__size > 0)                                             \
        {                                                                   \
            __list2_head->__prev = __list1->__head->__prev;                 \
            __list2_tail->__next = __list1->__head;                         \
            __list2_head->__prev->__next = __list2_head;                    \
            __list2_tail->__next->__prev = __list2_tail;                    \
            \
            __list2->__head->__next = __list2->__head;                      \
            __list2->__head->__prev = __list2->__head;                      \
            __list1->__size += __list2->__size;                             \
            __list2->__size -= __list2->__size;                             \
        }                                                                   \
    } while(0)

#define cm_list_clear(list)                                                 \
    do {                                                                    \
        __cm_list* __cl_list = (list);                                      \
        while(__cl_list->__size > 0)                                        \
        {                                                                   \
            cm_list_remove(__cl_list, __cl_list->__head->__next);           \
        }                                                                   \
    } while(0)

#define cm_list_data_ptr(pos, type) ((type*)((pos) + 1))
#define cm_list_data(pos, type)     (*(type*)((pos) + 1))

static __unused __cm_list_node* __cm_list_head_sub(__cm_list* list)
{
    return list->__size > 0 ? list->__head->__next : NULL;
}
static __unused __cm_list_node* __cm_list_tail_sub(__cm_list* list)
{
    return list->__size > 0 ? list->__head->__prev : NULL;
}
#define cm_list_head(list) __cm_list_head_sub(list)
#define cm_list_tail(list) __cm_list_tail_sub(list)

static __unused __cm_list_node* __cm_list_next_sub(__cm_list* list, __cm_list_node* node)
{
    return node->__next != list->__head ? node->__next : NULL;
}
static __unused __cm_list_node* __cm_list_prev_sub(__cm_list* list, __cm_list_node* node)
{
    return node->__prev != list->__head ? node->__prev : NULL;
}
#define cm_list_next(list, pos) __cm_list_next_sub(list, node)
#define cm_list_prev(list, pos) __cm_list_prev_sub(list, node)

#define cm_list_reverse(list)                                               \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        __cm_list_node* __node = __list->__head->__next;                    \
        \
        while(__node != __list->__head)                                     \
        {                                                                   \
            cm_basic_swap(__cm_list_node*, &__node->__next, &__node->__prev); \
            __node = __node->__prev;                                        \
        }                                                                   \
        cm_basic_swap(__cm_list_node*, &__list->__head->__next, &__list->__head->__prev); \
    } while(0)

#define cm_list_sort(list, type, cmp)                                       \
    do {                                                                    \
        __cm_list* __list = (list);                                         \
        __cm_list_node* __node1;                                            \
        __cm_list_node* __node2;                                            \
        size_t __step;                                                      \
        size_t __i;                                                         \
        \
        for(__step = 1; __step < cm_list_size(__list); __step *= 2)         \
        {                                                                   \
            __node1 = __list->__head->__next;                               \
            __node2 = __list->__head->__next;                               \
            \
            while(__node2 != __list->__head)                                \
            {                                                               \
                __node1 = __node2;                                          \
                for(__i = 0; __i < __step && __node2 != __list->__head; __i++) \
                {                                                           \
                    __node2 = __node2->__next;                              \
                }                                                           \
                __i = 0;                                                    \
                while(__node1 != __node2 && __i < __step && __node2 != __list->__head) \
                {                                                           \
                    if(cmp(cm_list_data(__node1, type), cm_list_data(__node2, type)) > 0) \
                    {                                                       \
                        __node2->__prev->__next = __node2->__next;          \
                        __node2->__next->__prev = __node2->__prev;          \
                        \
                        __node2->__prev = __node1->__prev;                  \
                        __node1->__prev->__next = __node2;                  \
                        __node2 = __node2->__next;                          \
                        \
                        __node1->__prev = __node1->__prev->__next;          \
                        __node1->__prev->__next = __node1;                  \
                        __i += 1;                                           \
                    } else __node1 = __node1->__next;                       \
                }                                                           \
                while((__i++) < __step && __node2 != __list->__head) __node2 = __node2->__next; \
            }                                                               \
        }                                                                   \
    } while(0)

/* heap (using vector) */
/******************************************************************************/
#define cm_heap_type __cm_vector_ptr

#define cm_heap_init(heap)      cm_vector_init(heap)
#define cm_heap_destroy(heap)   cm_vector_destroy(heap)

#define cm_heap_clear(heap)         cm_vector_clear(heap)
#define cm_heap_size(heap)          cm_vector_size(heap)
#define cm_heap_getmax(heap, type)  cm_vector_data_at(heap, 0, type)

#define cm_heap_insert(heap, type, data, cmp)                               \
    do {                                                                    \
        __cm_vector* __heap = (heap);                                       \
        type __h_data = (data);                                             \
        size_t __current = cm_vector_size(__heap);                          \
        \
        cm_vector_append(__heap, type, __h_data);                           \
        while(__current > 0)                                                \
        {                                                                   \
            type* __ptr_child = cm_vector_data_ptr_at(__heap, __current, type); \
            type* __ptr_parent = cm_vector_data_ptr_at(__heap, (__current - 1) / 2, type); \
            \
            if(cmp(*__ptr_child, *__ptr_parent) > 0)                        \
            {                                                               \
                cm_basic_swap(type, __ptr_child, __ptr_parent);             \
                __current -= 1;                                             \
                __current /= 2;                                             \
            }                                                               \
            else break;                                                     \
        }                                                                   \
    } while(0)

#define cm_heap_delmax(heap, type, cmp)                                     \
    do {                                                                    \
        __cm_vector* __heap = (heap);                                       \
        size_t __current = 0;                                               \
        size_t __child1;                                                    \
        size_t __child2;                                                    \
        size_t __max;                                                       \
        type* __ptr_cmp = NULL;                                             \
        type* __ptr_max = NULL;                                             \
        \
        cm_vector_data_at(__heap, 0, type) = cm_vector_lastdata(__heap, type); \
        cm_vector_remove_last(__heap, type);                                \
        \
        while(1)                                                            \
        {                                                                   \
            __child1 = __current * 2 + 1;                                   \
            __child2 = __current * 2 + 2;                                   \
            __max = __current;                                              \
            \
            if(__child1 < cm_vector_size(__heap))                           \
            {                                                               \
                __ptr_max = cm_vector_data_ptr_at(__heap, __max, type);     \
                __ptr_cmp = cm_vector_data_ptr_at(__heap, __child1, type);  \
                (cmp(*__ptr_max, *__ptr_cmp) < 0) ? (__max = __child1) : 0; \
            }                                                               \
            if(__child2 < cm_vector_size(__heap))                           \
            {                                                               \
                __ptr_max = cm_vector_data_ptr_at(__heap, __max, type);     \
                __ptr_cmp = cm_vector_data_ptr_at(__heap, __child2, type);  \
                (cmp(*__ptr_max, *__ptr_cmp) < 0) ? (__max = __child2) : 0; \
            }                                                               \
            \
            if(__max != __current)                                          \
            {                                                               \
                __ptr_max = cm_vector_data_ptr_at(__heap, __max, type);     \
                cm_basic_swap(type, __ptr_max, cm_vector_data_ptr_at(__heap, __current, type)); \
                __current = __max;                                          \
            }                                                               \
            else break;                                                     \
        }                                                                   \
    } while(0)

/* skew heap */
/******************************************************************************/
typedef struct __cm_skew_heap_struct
{
    struct __cm_skew_heap_node_struct* __rootnode;
    size_t __size;
} __cm_skew_heap, *__cm_skew_heap_ptr;

typedef struct __cm_skew_heap_node_struct
{
    struct __cm_skew_heap_node_struct* __child[2];
} __cm_skew_heap_node, *__cm_skew_heap_node_ptr;

#define cm_skew_heap_type __cm_skew_heap_ptr

#define cm_skew_heap_init(heap)                                             \
    do {                                                                    \
        __cm_skew_heap* __heap;                                             \
        __heap = (__cm_skew_heap*)__cm_malloc(sizeof(__cm_skew_heap));      \
        __heap->__rootnode = NULL;                                          \
        __heap->__size = 0;                                                 \
        (heap) = __heap;                                                    \
    } while(0)

static __unused int __cm_skew_heap_destroy_sub(__cm_skew_heap_node* node)
{
    if(node)
    {
        __cm_skew_heap_destroy_sub(node->__child[0]);
        __cm_skew_heap_destroy_sub(node->__child[1]);
        __cm_free(node);
    }
    return 1;
}
#define cm_skew_heap_destroy(heap)                                          \
    do {                                                                    \
        __cm_skew_heap* __heap = (heap);                                    \
        __cm_skew_heap_destroy_sub(__heap->__rootnode);                     \
        __cm_free(__heap);                                                  \
    } while(0)

#define cm_skew_heap_clear(heap)                                            \
    do {                                                                    \
        __cm_skew_heap* __heap = (heap);                                    \
        __cm_skew_heap_destroy_sub(__heap->__rootnode);                     \
        __heap->__size = 0;                                                 \
    } while(0)

#define cm_skew_heap_size(heap)         ((heap)->__size)
#define cm_skew_heap_getmax(heap, type) (*(type*)((heap)->__rootnode + 1))

#define __cm_skew_heap_merge_node(node1, node2, type, cmp, merge_result_node) \
    do {                                                                    \
        __cm_skew_heap_node* __node1 = (node1);                             \
        __cm_skew_heap_node* __node2 = (node2);                             \
        __cm_skew_heap_node* __main_node = __node1;                         \
        __cm_skew_heap_node* __subs_node = __node2;                         \
        __cm_skew_heap_node* __tmp_node;                                    \
        \
        if(!__node1) { (merge_result_node) = __node2; break; }              \
        if(!__node2) { (merge_result_node) = __node1; break; }              \
        \
        if(cmp(*(type*)(__main_node + 1), *(type*)(__subs_node + 1)) < 0)   \
        {                                                                   \
            cm_basic_swap(__cm_skew_heap_node*, &__main_node, &__subs_node);\
        }                                                                   \
        __node1 = __main_node;                                              \
        __node2 = __subs_node;                                              \
        \
        while(__node1->__child[1] != NULL && __node2 != NULL)               \
        {                                                                   \
            if(cmp(*(type*)(__node2 + 1), *(type*)(__node1->__child[1] + 1)) < 0) \
            {                                                               \
                __node1 = __node1->__child[1];                              \
            }                                                               \
            else                                                            \
            {                                                               \
                __tmp_node = __node2->__child[1];                           \
                __node2->__child[1] = __node1->__child[1];                  \
                __node1->__child[1] = __node2;                              \
                __node1 = __node1->__child[1];                              \
                __node2 = __tmp_node;                                       \
            }                                                               \
        }                                                                   \
        if(!__node1->__child[1])                                            \
        {                                                                   \
            __node1->__child[1] = __node2;                                  \
        }                                                                   \
        __node1 = __main_node;                                              \
        while(__node1)                                                      \
        {                                                                   \
            cm_basic_swap(__cm_skew_heap_node*, &__node1->__child[0], &__node1->__child[1]); \
            __node1 = __node1->__child[0];                                  \
        }                                                                   \
        (merge_result_node) = __main_node;                                  \
    } while(0)

#define cm_skew_heap_insert(heap, type, data, cmp)                          \
    do {                                                                    \
        __cm_skew_heap* __zheap = (heap);                                   \
        __cm_skew_heap_node* __newnode;                                     \
        \
        __newnode = (__cm_skew_heap_node*)__cm_malloc(sizeof(__cm_skew_heap_node) + sizeof(type)); \
        \
        *(type*)(__newnode + 1) = data;                                     \
        __newnode->__child[0] = NULL;                                       \
        __newnode->__child[1] = NULL;                                       \
        __cm_skew_heap_merge_node(__zheap->__rootnode, __newnode, type, cmp, __zheap->__rootnode); \
        __zheap->__size += 1;                                               \
    } while(0)

#define cm_skew_heap_delmax(heap, type, cmp)                                \
    do {                                                                    \
        __cm_skew_heap* __zheap = (heap);                                   \
        __cm_skew_heap_node* __oldnode = __zheap->__rootnode;               \
        \
        __cm_skew_heap_merge_node(__oldnode->__child[0], __oldnode->__child[1], type, cmp, __zheap->__rootnode); \
        __cm_free(__oldnode);                                               \
        __zheap->__size -= 1;                                               \
    } while(0)

#define cm_skew_heap_merge(heap1, heap2, type, cmp)                         \
    do {                                                                    \
        __cm_skew_heap* __zheap1 = (heap1);                                 \
        __cm_skew_heap* __zheap2 = (heap2);                                 \
        \
        __cm_skew_heap_merge_node(__zheap1->__rootnode, __zheap2->__rootnode, type, cmp, __zheap1->__rootnode); \
        __zheap2->__rootnode = NULL;                                        \
        __zheap1->__size += __zheap2->__size;                               \
        __zheap2->__size -= __zheap2->__size;                               \
    } while(0)

/* binomial heap */
/******************************************************************************/
typedef struct __cm_binomial_heap_node_struct
{
    struct __cm_binomial_heap_node_struct* __children_head;
    struct __cm_binomial_heap_node_struct* __prev;
    struct __cm_binomial_heap_node_struct* __next;
    size_t __index;
} __cm_binomial_heap_node, *__cm_binomial_heap_node_ptr;

typedef struct __cm_binomial_heap_struct
{
    struct __cm_binomial_heap_node_struct* __rootnode;
    struct __cm_binomial_heap_node_struct* __maxnode;
    size_t __size;
} __cm_binomial_heap, *__cm_binomial_heap_ptr;

#define cm_binomial_heap_type __cm_binomial_heap_ptr

#define cm_binomial_heap_init(heap)                                         \
    do {                                                                    \
        __cm_binomial_heap* __heap;                                         \
        \
        __heap = (__cm_binomial_heap*)__cm_malloc(sizeof(__cm_binomial_heap) + sizeof(__cm_binomial_heap_node)); \
        __heap->__rootnode = (__cm_binomial_heap_node*)(__heap + 1);        \
        \
        __heap->__rootnode->__children_head = NULL;                         \
        __heap->__rootnode->__prev = NULL;                                  \
        __heap->__rootnode->__next = NULL;                                  \
        __heap->__rootnode->__index = 0;                                    \
        __heap->__size = 0;                                                 \
        __heap->__maxnode = NULL;                                           \
        (heap) = __heap;                                                    \
    } while(0)

static __unused int __cm_binomial_heap_destroy_sub(__cm_binomial_heap_node* node)
{
    __cm_binomial_heap_node* iter_node;

    if(node->__children_head)
    {
        node->__children_head->__prev->__next = NULL;
        iter_node = node->__children_head;
        while(iter_node)
        {
            __cm_binomial_heap_node* next_node = iter_node->__next;
            __cm_binomial_heap_destroy_sub(iter_node);
            iter_node = next_node;
        }
    }
    if(node->__next != NULL) /* not root */
        __cm_free(node);
    return 0;
}
#define cm_binomial_heap_destroy(heap)                                      \
    do {                                                                    \
        __cm_binomial_heap* __heap = (heap);                                \
        __cm_binomial_heap_destroy_sub(__heap->__rootnode);                 \
        __cm_free(__heap);                                                  \
    } while(0)

#define cm_binomial_heap_clear(heap)                                        \
    do {                                                                    \
        __cm_binomial_heap* __heap = (heap);                                \
        __cm_binomial_heap_node* iter_node;                                 \
        \
        iter_node = __heap->__rootnode->__children_head;                    \
        __cm_binomial_heap_node* iter_node = node->__children_head;         \
        while(!iter_node)                                                   \
        {                                                                   \
            __cm_binomial_heap_node* next_node = iter_node->__next;         \
            __cm_binomial_heap_destroy_sub(iter_node);                      \
            iter_node = next_node;                                          \
        }                                                                   \
        __heap->__rootnode->__children_head = NULL;                         \
        __heap->__rootnode->__index = 0;                                    \
        __heap->__size = 0;                                                 \
    } while(0)

#define cm_binomial_heap_size(heap)         ((heap)->__size)
#define cm_binomial_heap_getmax(heap, type) (*(type*)((heap)->__maxnode + 1))

#define __cm_binomial_heap_merge_node(node1, node2, type, cmp, result_node) \
    do {                                                                    \
        __cm_binomial_heap_node* __node1 = (node1);                         \
        __cm_binomial_heap_node* __node2 = (node2);                         \
        if(cmp(*(type*)(__node1 + 1), *(type*)(__node2 + 1)) >= 0)          \
        {                                                                   \
            if(__node1->__index > 0)                                        \
            {                                                               \
                __node2->__next = __node1->__children_head;                 \
                __node2->__prev = __node1->__children_head->__prev;         \
                __node2->__next->__prev = __node2;                          \
                __node2->__prev->__next = __node2;                          \
                __node1->__index += 1;                                      \
            }                                                               \
            else                                                            \
            {                                                               \
                __node2->__prev = __node2;                                  \
                __node2->__next = __node2;                                  \
                __node1->__children_head = __node2;                         \
                __node1->__index += 1;                                      \
            }                                                               \
            (result_node) = __node1;                                        \
        }                                                                   \
        else                                                                \
        {                                                                   \
            if(__node2->__index > 0)                                        \
            {                                                               \
                __node1->__next = __node2->__children_head;                 \
                __node1->__prev = __node2->__children_head->__prev;         \
                __node1->__next->__prev = __node1;                          \
                __node1->__prev->__next = __node1;                          \
                __node2->__index += 1;                                      \
            }                                                               \
            else                                                            \
            {                                                               \
                __node1->__prev = __node1;                                  \
                __node1->__next = __node1;                                  \
                __node2->__children_head = __node1;                         \
                __node2->__index += 1;                                      \
            }                                                               \
            (result_node) = __node2;                                        \
        }                                                                   \
    } while(0)

#define __cm_binomial_heap_merge_list(node, list, type, cmp)                \
    do {                                                                    \
        __cm_binomial_heap_node* __rootnode = (node);                       \
        __cm_binomial_heap_node* __list1_head = (list);                     \
        __cm_binomial_heap_node* __list2_head = __rootnode->__children_head;\
        __cm_binomial_heap_node* __list1_last;                              \
        __cm_binomial_heap_node* __list2_last;                              \
        __cm_binomial_heap_node* __tempnode1;                               \
        __cm_binomial_heap_node* __tempnode2;                               \
        __cm_binomial_heap_node* __carrynode = NULL;                        \
        __cm_binomial_heap_node __newlist;                                  \
        size_t __index = 0;                                                 \
        size_t __case;                                                      \
        \
        if(!__list1_head) { __rootnode->__children_head = __list2_head; break; } \
        if(!__list2_head) { __rootnode->__children_head = __list1_head; break; } \
        __list1_last = __list1_head->__prev;                                \
        __list2_last = __list2_head->__prev;                                \
        __list1_last->__next = NULL;                                        \
        __list2_last->__next = NULL;                                        \
        __newlist.__next = &__newlist;                                      \
        __newlist.__prev = &__newlist;                                      \
        while(__carrynode || (__list1_head && __list2_head))                \
        {                                                                   \
            __case = 0;                                                     \
            __case += 1 * (__list1_head && __index == __list1_head->__index); \
            __case += 2 * (__list2_head && __index == __list2_head->__index); \
            __case += 4 * (__carrynode != NULL);                            \
            switch(__case)                                                  \
            {                                                               \
                case 1: {                                                   \
                            __tempnode1 = __list1_head->__next;             \
                            __list1_head->__prev = __newlist.__prev;        \
                            __newlist.__prev->__next = __list1_head;        \
                            __newlist.__prev = __list1_head;                \
                            __list1_head = __tempnode1;                     \
                            break;                                          \
                        }                                                   \
                case 2: {                                                   \
                            __tempnode2 = __list2_head->__next;             \
                            __list2_head->__prev = __newlist.__prev;        \
                            __newlist.__prev->__next = __list2_head;        \
                            __newlist.__prev = __list2_head;                \
                            __list2_head = __tempnode2;                     \
                            break;                                          \
                        }                                                   \
                case 3: {                                                   \
                            __tempnode1 = __list1_head->__next;             \
                            __tempnode2 = __list2_head->__next;             \
                            __cm_binomial_heap_merge_node(__list1_head, __list2_head, type, cmp, __carrynode); \
                            __list1_head = __tempnode1;                     \
                            __list2_head = __tempnode2;                     \
                            break;                                          \
                        }                                                   \
                case 4: {                                                   \
                            __carrynode->__prev = __newlist.__prev;         \
                            __newlist.__prev->__next = __carrynode;         \
                            __newlist.__prev = __carrynode;                 \
                            __carrynode = NULL;                             \
                            break;                                          \
                        }                                                   \
                case 5: {                                                   \
                            __tempnode1 = __list1_head->__next;             \
                            __cm_binomial_heap_merge_node(__carrynode, __list1_head, type, cmp, __carrynode);\
                            __list1_head = __tempnode1;                     \
                            break;                                          \
                        }                                                   \
                case 6: {                                                   \
                            __tempnode2 = __list2_head->__next;             \
                            __cm_binomial_heap_merge_node(__carrynode, __list2_head, type, cmp, __carrynode);\
                            __list2_head = __tempnode2;                     \
                            break;                                          \
                        }                                                   \
                case 7: {                                                   \
                            __carrynode->__prev = __newlist.__prev;         \
                            __newlist.__prev->__next = __carrynode;         \
                            __newlist.__prev = __carrynode;                 \
                            \
                            __tempnode1 = __list1_head->__next;             \
                            __tempnode2 = __list2_head->__next;             \
                            __cm_binomial_heap_merge_node(__list1_head, __list2_head, type, cmp, __carrynode); \
                            __list1_head = __tempnode1;                     \
                            __list2_head = __tempnode2;                     \
                            break;                                          \
                        }                                                   \
            }                                                               \
            __index += 1;                                                   \
        }                                                                   \
        __newlist.__prev->__next = &__newlist;                              \
        \
        if(__list1_head)                                                    \
        {                                                                   \
            __list1_head->__prev = __newlist.__prev;                        \
            __list1_last->__next = &__newlist;                              \
            __list1_head->__prev->__next = __list1_head;                    \
            __list1_last->__next->__prev = __list1_last;                    \
        }                                                                   \
        if(__list2_head)                                                    \
        {                                                                   \
            __list2_head->__prev = __newlist.__prev;                        \
            __list2_last->__next = &__newlist;                              \
            __list2_head->__prev->__next = __list2_head;                    \
            __list2_last->__next->__prev = __list2_last;                    \
        }                                                                   \
        __newlist.__next->__prev = __newlist.__prev;                        \
        __newlist.__prev->__next = __newlist.__next;                        \
        __rootnode->__children_head = __newlist.__next;                     \
    } while(0)

#define cm_binomial_heap_insert(heap, type, data, cmp)                      \
    do {                                                                    \
        __cm_binomial_heap* __heap = (heap);                                \
        __cm_binomial_heap_node* __newnode;                                 \
        type __data = (data);                                               \
        \
        __newnode = (__cm_binomial_heap_node*)__cm_malloc(sizeof(__cm_binomial_heap_node) + sizeof(type)); \
        __newnode->__index = 0;                                             \
        __newnode->__children_head = NULL;                                  \
        __newnode->__prev = __newnode;                                      \
        __newnode->__next = __newnode;                                      \
        *(type*)(__newnode + 1) = __data;                                   \
        \
        if(!__heap->__maxnode || cmp(__data, *(type*)(__heap->__maxnode + 1)) >= 0) \
        {                                                                   \
            __heap->__maxnode = __newnode;                                  \
        }                                                                   \
        __cm_binomial_heap_merge_list(__heap->__rootnode, __newnode, type, cmp); \
        __heap->__size += 1;                                                \
    } while(0)

#define __cm_binomial_heap_update_maxnode(heap, type, cmp)                  \
    do {                                                                    \
        __cm_binomial_heap* __uheap = (heap);                               \
        __cm_binomial_heap_node* __unode;                                   \
        if(__uheap->__size > 0)                                             \
        {                                                                   \
            __uheap->__maxnode = __uheap->__rootnode->__children_head;      \
            __unode = __uheap->__maxnode->__next;                           \
            while(__unode != __uheap->__rootnode->__children_head)          \
            {                                                               \
                if(cmp(*(type*)(__unode + 1), *(type*)(__uheap->__maxnode + 1)) > 0) \
                {                                                           \
                    __uheap->__maxnode = __unode;                           \
                }                                                           \
                __unode = __unode->__next;                                  \
            }                                                               \
        } else __uheap->__maxnode = NULL;                                   \
    } while(0)

#define cm_binomial_heap_delmax(heap, type, cmp)                            \
    do {                                                                    \
        __cm_binomial_heap* __heap = (heap);                                \
        __cm_binomial_heap_node* __delnode = __heap->__maxnode;             \
        \
        if(__delnode->__next != __delnode)                                  \
        {                                                                   \
            __delnode->__prev->__next = __delnode->__next;                  \
            __delnode->__next->__prev = __delnode->__prev;                  \
            if(__delnode == __heap->__rootnode->__children_head)            \
            {                                                               \
                __heap->__rootnode->__children_head = __delnode->__next;    \
            }                                                               \
            __cm_binomial_heap_merge_list(__heap->__rootnode, __delnode->__children_head, type, cmp); \
        }                                                                   \
        else __heap->__rootnode->__children_head = __delnode->__children_head; \
        __cm_free(__delnode);                                               \
        \
        __heap->__size -= 1;                                                \
        __cm_binomial_heap_update_maxnode(__heap, type, cmp);               \
    } while(0)

#define cm_binomial_heap_merge(heap1, heap2, type, cmp)                     \
    do {                                                                    \
        __cm_binomial_heap* __heap1 = (heap1);                              \
        __cm_binomial_heap* __heap2 = (heap2);                              \
        \
        __cm_binomial_heap_merge_list(__heap1->__rootnode, __heap2->__rootnode->__children_head, type, cmp); \
        __heap1->__size += __heap2->__size;                                 \
        __heap2->__size -= __heap2->__size;                                 \
        __cm_binomial_heap_update_maxnode(__heap1, type, cmp);              \
        __heap2->__maxnode = NULL;                                          \
        __heap2->__rootnode->__children_head = NULL;                        \
    } while(0)

/* pairing heap */
/******************************************************************************/
typedef struct __cm_pairing_heap_node_struct
{
    struct __cm_pairing_heap_node_struct* __parent;
    struct __cm_pairing_heap_node_struct* __children_head;
    struct __cm_pairing_heap_node_struct* __prev;
    struct __cm_pairing_heap_node_struct* __next;
} __cm_pairing_heap_node, *__cm_pairing_heap_node_ptr;

typedef struct __cm_pairing_heap_struct
{
    struct __cm_pairing_heap_node_struct* __rootnode;
    struct __cm_pairing_heap_node_struct* __lastnode;
    size_t __size;
} __cm_pairing_heap, *__cm_pairing_heap_ptr;

#define cm_pairing_heap_type        __cm_pairing_heap_ptr
#define cm_pairing_heap_node_type   __cm_pairing_heap_node_ptr

#define cm_pairing_heap_init(heap)                                          \
    do {                                                                    \
        __cm_pairing_heap* __heap = (__cm_pairing_heap*)__cm_malloc(sizeof(__cm_pairing_heap)); \
        __heap->__rootnode = NULL;                                          \
        __heap->__lastnode = NULL;                                          \
        __heap->__size = 0;                                                 \
        (heap) = __heap;                                                    \
    } while(0)

static __unused int __cm_pairing_heap_destroy_sub(__cm_pairing_heap_node* node)
{
    __cm_pairing_heap_node* iter_node = node->__children_head;

    while(iter_node)
    {
        __cm_pairing_heap_node* next_node = iter_node->__next;
        __cm_pairing_heap_destroy_sub(iter_node);
        iter_node = next_node;
    }
    __cm_free(node);
    return 0;
}
#define cm_pairing_heap_destroy(heap)                                       \
    do {                                                                    \
        __cm_pairing_heap* __heap = (heap);                                 \
        \
        if(__heap->__rootnode != NULL)                                      \
        __cm_pairing_heap_destroy_sub(__heap->__rootnode);                  \
        __cm_free(__heap);                                                  \
    } while(0)

#define cm_pairing_heap_lastnode(heap)          ((heap)->__lastnode)
#define cm_pairing_heap_size(heap)              ((heap)->__size)
#define cm_pairing_heap_getmax(heap, type)      (*(type*)((heap)->__rootnode + 1))

#define __cm_pairing_heap_merge_node(node1, node2, type, cmp, result_node)  \
    do {                                                                    \
        __cm_pairing_heap_node* __mnode1 = (node1);                         \
        __cm_pairing_heap_node* __mnode2 = (node2);                         \
        \
        if(!__mnode1) { (result_node) = __mnode2; break; }                  \
        if(!__mnode2) { (result_node) = __mnode1; break; }                  \
        if(cmp(*(type*)(__mnode1 + 1), *(type*)(__mnode2 + 1)) >= 0)        \
        {                                                                   \
            if(__mnode1->__children_head != NULL)                           \
            {                                                               \
                __mnode2->__next = __mnode1->__children_head;               \
                __mnode2->__prev = NULL;                                    \
                __mnode1->__children_head->__prev = __mnode2;               \
                __mnode1->__children_head = __mnode2;                       \
            } else {                                                        \
                __mnode2->__prev = NULL;                                    \
                __mnode2->__next = NULL;                                    \
                __mnode1->__children_head = __mnode2;                       \
            }                                                               \
            __mnode2->__parent = __mnode1;                                  \
            (result_node) = __mnode1;                                       \
        } else {                                                            \
            if(__mnode2->__children_head != NULL)                           \
            {                                                               \
                __mnode1->__next = __mnode2->__children_head;               \
                __mnode1->__prev = NULL;                                    \
                __mnode2->__children_head->__prev = __mnode1;               \
                __mnode2->__children_head = __mnode1;                       \
            } else {                                                        \
                __mnode1->__prev = NULL;                                    \
                __mnode1->__next = NULL;                                    \
                __mnode2->__children_head = __mnode1;                       \
            }                                                               \
            __mnode1->__parent = __mnode2;                                  \
            (result_node) = __mnode2;                                       \
        }                                                                   \
    } while(0)

#define __cm_pairing_heap_merge_list(list_head, type, cmp, result_node)     \
    do {                                                                    \
        __cm_pairing_heap_node* __next_node = (list_head);                  \
        __cm_pairing_heap_node* __merge_node;                               \
        __cm_pairing_heap_node* __current_node;                             \
        __cm_pairing_heap_node* __temp_list = NULL;                         \
        \
        if(!__next_node || !__next_node->__next) { (result_node) = __next_node; break; } \
        \
        while(__next_node)                                                  \
        {                                                                   \
            if(!__next_node->__next)                                        \
            {                                                               \
                __next_node->__next = __temp_list;                          \
                __temp_list = __next_node;                                  \
                break;                                                      \
            }                                                               \
            __current_node = __next_node;                                   \
            __next_node = __next_node->__next->__next;                      \
            \
            __cm_pairing_heap_merge_node(__current_node, __current_node->__next, type, cmp, __merge_node); \
            __merge_node->__next = __temp_list;                             \
            __temp_list = __merge_node;                                     \
        }                                                                   \
        \
        while(__temp_list->__next != NULL)                                  \
        {                                                                   \
            __next_node = __temp_list->__next->__next;                      \
            \
            __cm_pairing_heap_merge_node(__temp_list, __temp_list->__next, type, cmp, __merge_node); \
            __merge_node->__next = __next_node;                             \
            __temp_list = __merge_node;                                     \
        }                                                                   \
        __temp_list->__prev = __temp_list->__next = NULL;                   \
        (result_node) = __temp_list;                                        \
    } while(0)

#define cm_pairing_heap_insert(heap, type, data, cmp)                       \
    do {                                                                    \
        __cm_pairing_heap* __heap = (heap);                                 \
        type __data = data;                                                 \
        __cm_pairing_heap_node* __newnode;                                  \
        \
        __newnode = (__cm_pairing_heap_node*)__cm_malloc(sizeof(__cm_pairing_heap_node) + sizeof(type)); \
        *(type*)(__newnode + 1) = __data;                                   \
        __newnode->__prev = NULL;                                           \
        __newnode->__next = NULL;                                           \
        __newnode->__children_head = NULL;                                  \
        __heap->__size += 1;                                                \
        __heap->__lastnode = __newnode;                                     \
        __cm_pairing_heap_merge_node(__heap->__rootnode, __heap->__lastnode, type, cmp, __heap->__rootnode); \
    } while(0)

#define cm_pairing_heap_delmax(heap, type, cmp)                             \
    do {                                                                    \
        __cm_pairing_heap* __heap = (heap);                                 \
        __cm_pairing_heap_node* __delnode = __heap->__rootnode;             \
        \
        __heap->__size -= 1;                                                \
        __cm_pairing_heap_merge_list(__delnode->__children_head, type, cmp, __heap->__rootnode); \
        __cm_free(__delnode);                                               \
    } while(0)

#define cm_pairing_heap_merge(heap1, heap2, type, cmp)                      \
    do {                                                                    \
        __cm_pairing_heap* __heap1 = (heap1);                               \
        __cm_pairing_heap* __heap2 = (heap2);                               \
        __cm_pairing_heap_merge_node(__heap1->__rootnode, __heap2->__rootnode, type, cmp, __heap1->__rootnode); \
        __heap2->__rootnode = NULL;                                         \
        __heap1->__size += __heap2->__size;                                 \
        __heap2->__size -= __heap2->__size;                                 \
    } while(0)

#define cm_pairing_heap_increase_key(heap, node, type, new_data, cmp)       \
    do {                                                                    \
        __cm_pairing_heap* __heap = (heap);                                 \
        __cm_pairing_heap_node* __incnode = (node);                         \
        \
        *(type*)(__incnode + 1) = (new_data);                               \
        if(__incnode != __heap->__rootnode)                                 \
        {                                                                   \
            if(__incnode->__parent && __incnode == __incnode->__parent->__children_head) \
            {                                                               \
                __incnode->__parent->__children_head = __incnode->__next;   \
            }                                                               \
            __incnode->__prev == NULL ? 0 : (__incnode->__prev->__next = __incnode->__next); \
            __incnode->__next == NULL ? 0 : (__incnode->__next->__prev = __incnode->__prev); \
            __incnode->__prev = NULL;                                       \
            __incnode->__next = NULL;                                       \
            __cm_pairing_heap_merge_node(__heap->__rootnode, __incnode, type, cmp, __heap->__rootnode); \
        }                                                                   \
    } while(0)

/* mapitem */
/******************************************************************************/
#define cm_mapitem_type_define(type, key_type, val_type)                    \
    typedef struct {                                                        \
        key_type __key;                                                     \
        val_type __val;                                                     \
    } type;

#define cm_mapitem_key(mapitem) ((mapitem).__key)
#define cm_mapitem_val(mapitem) ((mapitem).__val)

#define cm_mapitem_basic_cmp(mapitem1, mapitem2)    cm_basic_cmp((mapitem1).__key, (mapitem2).__key)
#define cm_mapitem_strcmp(mapitem1, mapitem2)       strcmp((mapitem1).__key, (mapitem2).__key)

/* sbtree */
/******************************************************************************/
typedef struct __cm_sbtree_struct
{
    struct __cm_sbtree_node_struct* __rootnode;
    struct __cm_sbtree_node_struct* __nullnode;
} __cm_sbtree, *__cm_sbtree_ptr;

typedef struct __cm_sbtree_node_struct
{
    struct __cm_sbtree_node_struct* __child[2];
    struct __cm_sbtree_node_struct* __parent;
    size_t __size;
} __cm_sbtree_node, *__cm_sbtree_node_ptr;

#define cm_sbtree_type         __cm_sbtree_ptr
#define cm_sbtree_node_type    __cm_sbtree_node_ptr

#define cm_sbtree_init(sbtree)                                              \
    do {                                                                    \
        __cm_sbtree* __sbtree;                                              \
        __sbtree = (__cm_sbtree*)__cm_malloc(sizeof(__cm_sbtree) + sizeof(__cm_sbtree_node));\
        __sbtree->__nullnode = (__cm_sbtree_node*)(__sbtree + 1);           \
        __sbtree->__rootnode = __sbtree->__nullnode;                        \
        \
        __sbtree->__nullnode->__child[0] = __sbtree->__nullnode;            \
        __sbtree->__nullnode->__child[1] = __sbtree->__nullnode;            \
        __sbtree->__nullnode->__parent = __sbtree->__nullnode;              \
        __sbtree->__nullnode->__size = 0;                                   \
        (sbtree) = __sbtree;                                                \
    } while(0)

static __unused int __cm_sbtree_destroy_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    if(node != sbtree->__nullnode)
    {
        __cm_sbtree_destroy_sub(sbtree, node->__child[0]);
        __cm_sbtree_destroy_sub(sbtree, node->__child[1]);
        __cm_free(node);
    }
    return 1;
}
#define cm_sbtree_destroy(sbtree)                                           \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        __cm_sbtree_destroy_sub(__sbtree, __sbtree->__rootnode);            \
        __cm_free(__sbtree);                                                \
    } while(0)

#define cm_sbtree_clear(sbtree)                                             \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        __cm_sbtree_destroy_sub(__sbtree, __sbtree->__rootnode);            \
        __sbtree->__rootnode = __sbtree->__nullnode;                        \
    } while(0)

#define cm_sbtree_size(sbtree)              ((sbtree)->__rootnode->__size)
#define cm_sbtree_node_data_ptr(node, type) ((type*)((node) + 1))
#define cm_sbtree_node_data(node, type)     (*(type*)((node) + 1))

#define __cm_sbtree_rotate_l(sbtree, node)                                  \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        __cm_sbtree_node* __rtnode = (node);                                \
        __cm_sbtree_node* __parent = __rtnode->__parent;                    \
        __cm_sbtree_node* __a = __rtnode;                                   \
        __cm_sbtree_node* __b = __rtnode->__child[1];                       \
        \
        __a->__child[1] = __b->__child[0];                                  \
        __b->__child[0] = __a;                                              \
        __a->__child[1]->__parent = __a;                                    \
        __b->__child[0]->__parent = __b;                                    \
        if(__parent != __sbtree->__nullnode)                                \
        {                                                                   \
            __parent->__child[(__parent->__child[1] == __a)] = __b;         \
            __b->__parent = __parent;                                       \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __sbtree->__rootnode = __b;                                     \
            __b->__parent = __sbtree->__nullnode;                           \
        }                                                                   \
        __b->__size = __a->__size;                                          \
        __a->__size = __a->__child[0]->__size + __a->__child[1]->__size + 1;\
    } while(0)

#define __cm_sbtree_rotate_r(sbtree, node)                                  \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        __cm_sbtree_node* __rtnode = (node);                                \
        __cm_sbtree_node* __parent = __rtnode->__parent;                    \
        __cm_sbtree_node* __a = __rtnode;                                   \
        __cm_sbtree_node* __b = __rtnode->__child[0];                       \
        \
        __a->__child[0] = __b->__child[1];                                  \
        __b->__child[1] = __a;                                              \
        __a->__child[0]->__parent = __a;                                    \
        __b->__child[1]->__parent = __b;                                    \
        if(__parent != __sbtree->__nullnode)                                \
        {                                                                   \
            __parent->__child[__parent->__child[1] == __a] = __b;           \
            __b->__parent = __parent;                                       \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __sbtree->__rootnode = __b;                                     \
            __b->__parent = __sbtree->__nullnode;                           \
        }                                                                   \
        __b->__size = __a->__size;                                          \
        __a->__size = __a->__child[0]->__size + __a->__child[1]->__size + 1;\
    } while(0)

static __unused int __cm_sbtree_maintain_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node, int flag)
{
    if(!flag)
    {
        if(node->__child[0]->__child[0]->__size > node->__child[1]->__size)
        {
            __cm_sbtree_rotate_r(sbtree, node);
        }
        else if(node->__child[0]->__child[1]->__size > node->__child[1]->__size)
        {
            __cm_sbtree_rotate_l(sbtree, node->__child[0]);
            __cm_sbtree_rotate_r(sbtree, node);
        }
        else return 1;
    }
    else
    {
        if(node->__child[1]->__child[1]->__size > node->__child[0]->__size)
        {
            __cm_sbtree_rotate_l(sbtree, node);
        }
        else if(node->__child[1]->__child[0]->__size > node->__child[0]->__size)
        {
            __cm_sbtree_rotate_r(sbtree, node->__child[1]);
            __cm_sbtree_rotate_l(sbtree, node);
        }
        else return 1;
    }
    __cm_sbtree_maintain_sub(sbtree, node->__child[0], 0);
    __cm_sbtree_maintain_sub(sbtree, node->__child[1], 1);
    __cm_sbtree_maintain_sub(sbtree, node, 0);
    __cm_sbtree_maintain_sub(sbtree, node, 1);
    return 1;
}

static __unused void __cm_sbtree_inc_size_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    while(node->__parent != sbtree->__nullnode)
    {
        node->__parent->__size += 1;
        node = node->__parent;
    }
    return;
}

#define cm_sbtree_insert_before(sbtree, pos, type, data)                    \
    do {                                                                    \
        __cm_sbtree* __sbtree= (sbtree);                                    \
        type __data = (data);                                               \
        __cm_sbtree_node* __pos = (pos);                                    \
        __cm_sbtree_node* __current_node;                                   \
        __cm_sbtree_node* __new_node;                                       \
        __cm_sbtree_node* __update_node;                                    \
        \
        __new_node = (__cm_sbtree_node*)__cm_malloc(sizeof(__cm_sbtree_node) + sizeof(type)); \
        \
        *(type*)(__new_node + 1) = __data;                                  \
        __new_node->__size = 1;                                             \
        __new_node->__child[0] = __sbtree->__nullnode;                      \
        __new_node->__child[1] = __sbtree->__nullnode;                      \
        __new_node->__parent = __sbtree->__nullnode;                        \
        \
        if(__sbtree->__rootnode == __sbtree->__nullnode)                    \
        {                                                                   \
            __sbtree->__rootnode = __new_node;                              \
            break;                                                          \
        }                                                                   \
        if(__pos == NULL)                                                   \
        {                                                                   \
            __current_node = __sbtree->__rootnode;                          \
            while(__current_node->__child[1] != __sbtree->__nullnode)       \
            {                                                               \
                __current_node = __current_node->__child[1];                \
            }                                                               \
            __current_node->__child[1] = __new_node;                        \
            __current_node->__child[1]->__parent = __current_node;          \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __current_node = __pos;                                         \
            if(__current_node->__child[0] == __sbtree->__nullnode)          \
            {                                                               \
                __current_node->__child[0] = __new_node;                    \
                __current_node->__child[0]->__parent = __current_node;      \
            }                                                               \
            else                                                            \
            {                                                               \
                __current_node = __current_node->__child[0];                \
                while(__current_node->__child[1] != __sbtree->__nullnode)   \
                {                                                           \
                    __current_node = __current_node->__child[1];            \
                }                                                           \
                __current_node->__child[1] = __new_node;                    \
                __current_node->__child[1]->__parent = __current_node;      \
            }                                                               \
        }                                                                   \
        \
        __update_node = __current_node;                                     \
        while(__update_node != __sbtree->__nullnode)                        \
        {                                                                   \
            __update_node->__size += 1;                                     \
            __update_node = __update_node->__parent;                        \
        }                                                                   \
        while(__current_node != __sbtree->__rootnode)                       \
        {                                                                   \
            __cm_sbtree_maintain_sub(__sbtree, __current_node, 0);          \
            __cm_sbtree_maintain_sub(__sbtree, __current_node, 1);          \
            __current_node = __current_node->__parent;                      \
        }                                                                   \
    } while(0)

#define cm_sbtree_insert(sbtree, type, data, cmp)                           \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        type __data = (data);                                               \
        __cm_sbtree_node* __current_node = __sbtree->__rootnode;            \
        __cm_sbtree_node* __new_node;                                       \
        \
        if(__sbtree->__rootnode == __sbtree->__nullnode)                    \
        {                                                                   \
            __new_node = (__cm_sbtree_node*)__cm_malloc(sizeof(__cm_sbtree_node) + sizeof(type)); \
            \
            *(type*)(__new_node + 1) = __data;                              \
            __new_node->__size = 1;                                         \
            __new_node->__child[0] = __sbtree->__nullnode;                  \
            __new_node->__child[1] = __sbtree->__nullnode;                  \
            __new_node->__parent = __sbtree->__nullnode;                    \
            __sbtree->__rootnode = __new_node;                              \
            break;                                                          \
        }                                                                   \
        else                                                                \
        {                                                                   \
            while(1)                                                        \
            {                                                               \
                int __cmp = cmp(__data, *(type*)(__current_node + 1));      \
                \
                if(__cmp == 0) break;                                       \
                \
                if(__current_node->__child[__cmp > 0] == __sbtree->__nullnode) \
                {                                                           \
                    __new_node = (__cm_sbtree_node*)__cm_malloc(sizeof(__cm_sbtree_node) + sizeof(type)); \
                    \
                    *(type*)(__new_node + 1) = __data;                      \
                    __new_node->__size = 1;                                 \
                    __new_node->__child[0] = __sbtree->__nullnode;          \
                    __new_node->__child[1] = __sbtree->__nullnode;          \
                    __new_node->__parent = __current_node;                  \
                    \
                    __current_node->__child[__cmp > 0] = __new_node;        \
                    __cm_sbtree_inc_size_sub(__sbtree, __new_node);         \
                    break;                                                  \
                }                                                           \
                __current_node = __current_node->__child[__cmp > 0];        \
            }                                                               \
            __current_node = __current_node->__parent;                      \
            while(__current_node != __sbtree->__nullnode)                   \
            {                                                               \
                if(__current_node->__child[0]->__size >= __current_node->__child[1]->__size) \
                {                                                           \
                    __cm_sbtree_maintain_sub(__sbtree, __current_node, 0);  \
                } else {                                                    \
                    __cm_sbtree_maintain_sub(__sbtree, __current_node, 1);  \
                }                                                           \
                __current_node = __current_node->__parent;                  \
            }                                                               \
        }                                                                   \
    } while(0)

#define cm_sbtree_search(sbtree, type, data, cmp, result_node)              \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        type __data = (data);                                               \
        __cm_sbtree_node* __current_node = __sbtree->__rootnode;            \
        \
        (result_node) = NULL;                                               \
        while(__current_node != __sbtree->__nullnode)                       \
        {                                                                   \
            int __cmp = cmp(__data, *(type*)(__current_node + 1));          \
            \
            if(__cmp < 0){ __current_node = __current_node->__child[0]; continue; } \
            if(__cmp > 0){ __current_node = __current_node->__child[1]; continue; } \
            (result_node) = __current_node;                                 \
            break;                                                          \
        }                                                                   \
    } while(0)

static __unused int __cm_sbtree_remove_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node, size_t size)
{
    __cm_sbtree_node* current_node = node;
    __cm_sbtree_node* parent_node;
    if(node->__size > 1)
    {
        if(current_node->__child[0] != sbtree->__nullnode)
        {
            current_node = current_node->__child[0];
            while(current_node->__child[1] != sbtree->__nullnode)
            {
                current_node = current_node->__child[1];
            }
        }
        else
        {
            current_node = current_node->__child[1];
            while(current_node->__child[0] != sbtree->__nullnode)
            {
                current_node = current_node->__child[0];
            }
        }
        memcpy(node + 1, current_node + 1, size);
        return __cm_sbtree_remove_sub(sbtree, current_node, size);
    }
    else
    {
        if(node->__parent == sbtree->__nullnode)
        {
            __cm_free(node);
            sbtree->__rootnode = sbtree->__nullnode;
            return 1;
        }

        parent_node = node->__parent;
        parent_node->__child[parent_node->__child[1] == node] =
            sbtree->__nullnode;
        while(parent_node != sbtree->__nullnode)
        {
            parent_node->__size -= 1;
            parent_node = parent_node->__parent;
        }
        __cm_free(node);
        return 1;
    }
    return 0;
}
#define cm_sbtree_remove(sbtree, node, type) __cm_sbtree_remove_sub(sbtree, node, sizeof(type))

static __unused __cm_sbtree_node* __cm_sbtree_node_at_sub(__cm_sbtree_node* node, size_t pos)
{
    if(pos < node->__child[0]->__size)
        return __cm_sbtree_node_at_sub(node->__child[0], pos);
    else if(pos > node->__child[0]->__size)
        return __cm_sbtree_node_at_sub(node->__child[1], pos - node->__child[0]->__size - 1);
    return node;
}
#define cm_sbtree_node_at(sbtree, pos) __cm_sbtree_node_at_sub((sbtree)->__rootnode, (pos))

static __unused __cm_sbtree_node* __cm_sbtree_node_head_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    while(node->__child[0] != sbtree->__nullnode)
        node = node->__child[0];
    return node;
}
static __unused __cm_sbtree_node* __cm_sbtree_node_tail_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    while(node->__child[1] != sbtree->__nullnode)
        node = node->__child[1];
    return node;
}
static __unused __cm_sbtree_node* __cm_sbtree_node_next_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    if(node->__child[1] != sbtree->__nullnode)
        return __cm_sbtree_node_head_sub(sbtree, node->__child[1]);
    else
    {
        while(node->__parent != sbtree->__nullnode)
        {
            if(node->__parent->__child[0] == node)
                return node->__parent;
            node = node->__parent;
        }
    }
    return NULL;
}
static __unused __cm_sbtree_node* __cm_sbtree_node_prev_sub(__cm_sbtree* sbtree, __cm_sbtree_node* node)
{
    if(node->__child[0] != sbtree->__nullnode)
        return __cm_sbtree_node_tail_sub(sbtree, node->__child[0]);
    else
    {
        while(node->__parent != sbtree->__nullnode)
        {
            if(node->__parent->__child[1] == node)
                return node->__parent;
            node = node->__parent;
        }
    }
    return NULL;
}

static __unused __cm_sbtree_node* __cm_sbtree_node_head_wrap_sub(__cm_sbtree* sbtree)
{
    return sbtree->__rootnode != sbtree->__nullnode ? __cm_sbtree_node_head_sub(sbtree, sbtree->__rootnode) : NULL;
}

static __unused __cm_sbtree_node* __cm_sbtree_node_tail_wrap_sub(__cm_sbtree* sbtree)
{
    return sbtree->__rootnode != sbtree->__nullnode ? __cm_sbtree_node_tail_sub(sbtree, sbtree->__rootnode) : NULL;
}

#define cm_sbtree_node_head(sbtree) __cm_sbtree_node_head_wrap_sub(sbtree)
#define cm_sbtree_node_tail(sbtree) __cm_sbtree_node_tail_wrap_sub(sbtree)

#define cm_sbtree_node_next(sbtree, node) __cm_sbtree_node_next_sub((sbtree), (node))
#define cm_sbtree_node_prev(sbtree, node) __cm_sbtree_node_prev_sub((sbtree), (node))

#define cm_sbtree_getmin(sbtree, type) (*(type*)(cm_sbtree_node_head(sbtree)+1))
#define cm_sbtree_getmax(sbtree, type) (*(type*)(cm_sbtree_node_tail(sbtree)+1))

#define cm_sbtree_delmin(sbtree, type)                                      \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        cm_sbtree_remove(__sbtree, cm_sbtree_node_head(__sbtree), type);    \
    } while(0)
#define cm_sbtree_delmax(sbtree, type)                                      \
    do {                                                                    \
        __cm_sbtree* __sbtree = (sbtree);                                   \
        cm_sbtree_remove(__sbtree, cm_sbtree_node_tail(__sbtree), type);    \
    } while(0)

/* splay tree */
/******************************************************************************/
typedef struct __cm_splay_tree_node_struct
{
    struct __cm_splay_tree_node_struct* __child[2];
    size_t __size;
} __cm_splay_tree_node, *__cm_splay_tree_node_ptr;

typedef struct __cm_splay_tree_struct
{
    struct __cm_splay_tree_node_struct* __rootnode;
} __cm_splay_tree, *__cm_splay_tree_ptr;

typedef __cm_splay_tree_ptr cm_splay_tree_type;
typedef __cm_splay_tree_node_ptr cm_splay_tree_node_type;

static __unused size_t __cm_splay_tree_node_size_sub(__cm_splay_tree_node* root)
{
    return (root ? root->__size : 0);
}

#define __cm_splay_tree_splay(root, type, data, cmp, result_new_root)       \
    do {                                                                    \
        int __dir;                                                          \
        size_t __size[2] = {0};                                             \
        type __sdata = (data);                                              \
        __cm_splay_tree_node *__sroot = (root), *__s[2], *__stemp, __sstored; \
        if (__sroot != NULL)                                                \
        {                                                                   \
            __sstored.__child[0] = __sstored.__child[1] = NULL;             \
            __s[0] = __s[1] = &__sstored;                                   \
            for(;;)                                                         \
            {                                                               \
                int __dir2;                                                 \
                __dir = cmp(__sdata, *(type*)(__sroot+1));                  \
                __dir = __dir ? __dir < 0 ? 0 : 1 : -1;                     \
                if (__dir == -1 || __sroot->__child[__dir] == NULL) break;  \
                if (__sroot->__child[__dir] != NULL) {                      \
                    __dir2 = cmp(__sdata, *(type*)(__sroot->__child[__dir]+1)); \
                    __dir2 = __dir2 ? __dir2 < 0 ? 0 : 1 : -1;              \
                    if (__dir == __dir2) {                                  \
                        __stemp = __sroot->__child[__dir];                  \
                        __sroot->__child[__dir] = __stemp->__child[!__dir]; \
                        __stemp->__child[!__dir] = __sroot;                 \
                        __sroot->__size = 1;                                \
                        __sroot->__size += __cm_splay_tree_node_size_sub(__sroot->__child[0]); \
                        __sroot->__size += __cm_splay_tree_node_size_sub(__sroot->__child[1]); \
                        __sroot = __stemp;                                  \
                    }                                                       \
                }                                                           \
                if (__sroot->__child[__dir] == NULL) break;                 \
                __size[!__dir] += 1 + __cm_splay_tree_node_size_sub(__sroot->__child[!__dir]); \
                __s[!__dir]->__child[__dir] = __sroot;                      \
                __s[!__dir] = __sroot;                                      \
                __sroot = __sroot->__child[__dir];                          \
            }                                                               \
            __size[0] += __cm_splay_tree_node_size_sub(__sroot->__child[0]);\
            __size[1] += __cm_splay_tree_node_size_sub(__sroot->__child[1]);\
            __sroot->__size = __size[0] + 1 + __size[1];                    \
            for (__dir = 0; __dir < 2; __dir++)                             \
            {                                                               \
                __s[__dir]->__child[!__dir] = NULL;                         \
                for (__stemp = __sstored.__child[!__dir]; __stemp; __stemp = __stemp->__child[!__dir]) \
                {                                                           \
                    __stemp->__size = __size[__dir];                        \
                    __size[__dir] -= 1 + __cm_splay_tree_node_size_sub(__stemp->__child[__dir]); \
                }                                                           \
                __s[__dir]->__child[!__dir] = __sroot->__child[__dir];      \
                __sroot->__child[__dir] = __sstored.__child[!__dir];        \
            }                                                               \
        }                                                                   \
        (result_new_root) = __sroot;                                        \
    } while(0)

#define __cm_splay_tree_splay_by_rank(root, rank, result_new_root)          \
    do {                                                                    \
        int __dir;                                                          \
        size_t __size[2] = {0}, __rank = rank;                              \
        __cm_splay_tree_node *__sroot = (root), *__s[2], *__stemp, __sstored; \
        if (__sroot != NULL)                                                \
        {                                                                   \
            __sstored.__child[0] = __sstored.__child[1] = NULL;             \
            __s[0] = __s[1] = &__sstored;                                   \
            for(;;)                                                         \
            {                                                               \
                int __dir2;                                                 \
                __dir = __rank - __cm_splay_tree_node_size_sub(__sroot->__child[0]); \
                __dir = __dir ? __dir < 0 ? 0 : 1 : -1;                     \
                if (__dir == -1) break;                                     \
                if (__dir)                                                  \
                __rank -= 1 + __cm_splay_tree_node_size_sub(__sroot->__child[0]); \
                __dir2 = __rank - __cm_splay_tree_node_size_sub(__sroot->__child[__dir]->__child[0]); \
                __dir2 = __dir2 ? __dir2 < 0 ? 0 : 1 : -1;                  \
                if (__dir == __dir2) {                                      \
                    if (__dir)                                              \
                    __rank -= 1 + __cm_splay_tree_node_size_sub(__sroot->__child[1]->__child[0]); \
                    __stemp = __sroot->__child[__dir];                      \
                    __sroot->__child[__dir] = __stemp->__child[!__dir];     \
                    __stemp->__child[!__dir] = __sroot;                     \
                    __sroot->__size = 1;                                    \
                    __sroot->__size += __cm_splay_tree_node_size_sub(__sroot->__child[0]); \
                    __sroot->__size += __cm_splay_tree_node_size_sub(__sroot->__child[1]); \
                    __sroot = __stemp;                                      \
                    if (__sroot->__child[__dir] == NULL) break;             \
                }                                                           \
                __size[!__dir] += 1 + __cm_splay_tree_node_size_sub(__sroot->__child[!__dir]); \
                __s[!__dir]->__child[__dir] = __sroot;                      \
                __s[!__dir] = __sroot;                                      \
                __sroot = __sroot->__child[__dir];                          \
            }                                                               \
            __size[0] += __cm_splay_tree_node_size_sub(__sroot->__child[0]);\
            __size[1] += __cm_splay_tree_node_size_sub(__sroot->__child[1]);\
            __sroot->__size = __size[0] + 1 + __size[1];                    \
            for (__dir = 0; __dir < 2; __dir++)                             \
            {                                                               \
                __s[__dir]->__child[!__dir] = NULL;                         \
                for (__stemp = __sstored.__child[!__dir]; __stemp; __stemp = __stemp->__child[!__dir]) \
                {                                                           \
                    __stemp->__size = __size[__dir];                        \
                    __size[__dir] -= 1 + __cm_splay_tree_node_size_sub(__stemp->__child[__dir]); \
                }                                                           \
                __s[__dir]->__child[!__dir] = __sroot->__child[__dir];      \
                __sroot->__child[__dir] = __sstored.__child[!__dir];        \
            }                                                               \
        }                                                                   \
        (result_new_root) = __sroot;                                        \
    } while(0)

#define cm_splay_tree_init(tree)                                            \
    do {                                                                    \
        __cm_splay_tree* __tree = (__cm_splay_tree*)__cm_malloc(sizeof(__cm_splay_tree)); \
        __tree->__rootnode = NULL;                                          \
        (tree) = __tree;                                                    \
    } while(0)

#define cm_splay_tree_destroy(tree)                                         \
    do {                                                                    \
        __cm_splay_tree* __d_tree = (tree);                                 \
        cm_splay_tree_clear(__d_tree);                                      \
        __cm_free(__d_tree);                                                \
    } while(0)

#define cm_splay_tree_clear(tree)                                           \
    do {                                                                    \
        __cm_splay_tree* __tree = (tree);                                   \
        while(__tree->__rootnode)                                           \
        {                                                                   \
            cm_splay_tree_delmin(tree);                                     \
        }                                                                   \
        __tree->__rootnode = NULL;                                          \
    } while(0)

#define cm_splay_tree_size(tree)                (__cm_splay_tree_node_size_sub(tree->__rootnode))
#define cm_splay_tree_node_data_ptr(node, type) ((type*)((node) + 1))
#define cm_splay_tree_node_data(node, type)     (*(type*)((node) + 1))

#define cm_splay_tree_insert(tree, type, data, cmp)                         \
    do {                                                                    \
        type __data = (data);                                               \
        __cm_splay_tree* __tree = (tree);                                   \
        __cm_splay_tree_node* __new_node;                                   \
        __new_node = (__cm_splay_tree_node*)__cm_malloc(sizeof(__cm_splay_tree_node) + sizeof(type)); \
        __new_node->__child[0] = NULL;                                      \
        __new_node->__child[1] = NULL;                                      \
        __new_node->__size = 1;                                             \
        *(type*)(__new_node + 1) = __data;                                  \
        if(__tree->__rootnode == NULL)                                      \
        {                                                                   \
            __tree->__rootnode = __new_node;                                \
        }                                                                   \
        else                                                                \
        {                                                                   \
            int __dir;                                                      \
            __cm_splay_tree_splay(__tree->__rootnode, type, __data, cmp, __tree->__rootnode); \
            __dir = cmp(__data, *(type*)(__tree->__rootnode + 1));          \
            __dir = __dir < 0 ? 0 : 1;                                      \
            __new_node->__child[__dir] = __tree->__rootnode->__child[__dir];\
            __tree->__rootnode->__child[__dir] = NULL;                      \
            __new_node->__child[!__dir] = __tree->__rootnode;               \
            __new_node->__size = 1 + __tree->__rootnode->__size;            \
            __tree->__rootnode->__size = __cm_splay_tree_node_size_sub(__tree->__rootnode->__child[!__dir]) + 1; \
            __tree->__rootnode = __new_node;                                \
        }                                                                   \
    } while(0)

#define cm_splay_tree_search(tree, type, data, cmp, result_node)            \
    do {                                                                    \
        type __data = (data);                                               \
        __cm_splay_tree* __tree = (tree);                                   \
        \
        __cm_splay_tree_splay(__tree->__rootnode, type, data, cmp, __tree->__rootnode); \
        if(cmp(__data, *(type*)(__tree->__rootnode + 1)) == 0)              \
        {                                                                   \
            (result_node) = __tree->__rootnode;                             \
        }                                                                   \
        else (result_node) = NULL;                                          \
    } while(0)

#define cm_splay_tree_remove(tree, node, type, cmp)                         \
    do {                                                                    \
        __cm_splay_tree* __tree = (tree);                                   \
        __cm_splay_tree_node* __node = (node);                              \
        __cm_splay_tree_splay(__tree->__rootnode, type, *(type*)(__node + 1), cmp, __tree->__rootnode); \
        if(__node->__child[1] != NULL)                                      \
        {                                                                   \
            __cm_splay_tree_splay_by_rank(__node->__child[1], 0, __node->__child[1]); \
            __node->__child[1]->__child[0] = __node->__child[0];            \
            __node->__child[1]->__size = __tree->__rootnode->__size - 1;    \
            __tree->__rootnode = __node->__child[1];                        \
        }                                                                   \
        else                                                                \
        {                                                                   \
            __tree->__rootnode = __node->__child[0];                        \
        }                                                                   \
        __cm_free(__node);                                                  \
    } while(0)

static __unused __cm_splay_tree_node* __cm_splay_tree_node_at_sub(__cm_splay_tree* tree, size_t pos)
{
    __cm_splay_tree_splay_by_rank(tree->__rootnode, pos, tree->__rootnode);
    return tree->__rootnode;
}

#define cm_splay_tree_node_at(tree, pos)        __cm_splay_tree_node_at_sub(tree, pos)
#define cm_splay_tree_data_at(tree, pos, type)  cm_splay_tree_node_data(cm_splay_tree_node_at(tree, pos), type)

static __unused __cm_splay_tree_node* __cm_splay_tree_getmin_sub(__cm_splay_tree* tree)
{
    __cm_splay_tree_splay_by_rank(tree->__rootnode, 0, tree->__rootnode);
    return tree->__rootnode;
}

static __unused __cm_splay_tree_node* __cm_splay_tree_getmax_sub(__cm_splay_tree* tree)
{
    __cm_splay_tree_splay_by_rank(tree->__rootnode, __cm_splay_tree_node_size_sub(tree->__rootnode) - 1, tree->__rootnode);
    return tree->__rootnode;
}

#define cm_splay_tree_getmin(tree, type)                                    \
    (*(type*)(__cm_splay_tree_getmin_sub(tree) + 1))

#define cm_splay_tree_getmax(tree, type)                                    \
    (*(type*)(__cm_splay_tree_getmax_sub(tree) + 1))

#define cm_splay_tree_delmax(tree)                                          \
    do {                                                                    \
        __cm_splay_tree* __tree = (tree);                                   \
        __cm_splay_tree_node* __root = __cm_splay_tree_getmax_sub(__tree);  \
        __tree->__rootnode = __root->__child[0];                            \
        __cm_free(__root);                                                  \
    } while(0)

#define cm_splay_tree_delmin(tree)                                          \
    do {                                                                    \
        __cm_splay_tree* __tree = (tree);                                   \
        __cm_splay_tree_node* __root = __cm_splay_tree_getmin_sub(__tree);  \
        __tree->__rootnode = __root->__child[1];                            \
        __cm_free(__root);                                                  \
    } while(0)

/* skiplist */
/******************************************************************************/
typedef struct __cm_skiplist_node_struct
{
    struct __cm_skiplist_node_struct** __next;
    struct __cm_skiplist_node_struct** __prev;
    size_t __level;
} __cm_skiplist_node, *__cm_skiplist_node_ptr;

typedef struct __cm_skiplist_struct
{
    struct __cm_skiplist_node_struct* __headnode;
    size_t __size;
} __cm_skiplist, *__cm_skiplist_ptr;

#define cm_skiplist_node_type   __cm_skiplist_node_ptr
#define cm_skiplist_type        __cm_skiplist_ptr

#define __cm_skiplist_level_limit 64

#define cm_skiplist_size(list)                  (list->__size)
#define cm_skiplist_node_data(node, type)       (*(type*)(node + 1))
#define cm_skiplist_node_data_ptr(node, type)   ((type*)(node + 1))

#define cm_skiplist_init(list)                                              \
    do {                                                                    \
        __cm_skiplist* __list;                                              \
        __list = (__cm_skiplist*)__cm_malloc(sizeof(__cm_skiplist) + sizeof(__cm_skiplist_node)); \
        __list->__size = 0;                                                 \
        __list->__headnode = (__cm_skiplist_node*)(__list + 1);             \
        __list->__headnode->__level = 0;                                    \
        __list->__headnode->__next = NULL;                                  \
        __list->__headnode->__prev = NULL;                                  \
        (list) = __list;                                                    \
    } while(0)

#define cm_skiplist_destroy(list)                                           \
    do {                                                                    \
        __cm_skiplist* __list = (list);                                     \
        __cm_skiplist_node* __nextnode;                                     \
        __cm_skiplist_node* __node = __list->__headnode->__next[0];         \
        while(__node != __list->__headnode)                                 \
        {                                                                   \
            __nextnode = __node->__next[0];                                 \
            __cm_free(__node);                                              \
            __node = __nextnode;                                            \
        }                                                                   \
    } while(0)

#define cm_skiplist_insert(list, type, data, cmp)                           \
    do {                                                                    \
        __cm_skiplist* __list = (list);                                     \
        type __data = (data);                                               \
        __cm_skiplist_node* __node;                                         \
        __cm_skiplist_node* __newnode;                                      \
        size_t __newnode_size;                                              \
        size_t __level = 1;                                                 \
        size_t __i;                                                         \
        \
        while(__level < __cm_skiplist_level_limit && (rand() & 1))          \
        {                                                                   \
            __level += 1;                                                   \
        }                                                                   \
        __newnode_size = sizeof(__cm_skiplist_node) + sizeof(type) + sizeof(void*) * 2 * __level; \
        __newnode = (__cm_skiplist_node*)__cm_malloc(__newnode_size);       \
        __newnode->__level = __level;                                       \
        __newnode->__next = (__cm_skiplist_node**)((type*)(__newnode + 1) + 1); \
        __newnode->__prev = (__cm_skiplist_node**)((type*)(__newnode + 1) + 1) + __level; \
        *(type*)(__newnode + 1) = __data;                                   \
        \
        if(__list->__headnode->__level < __level)                           \
        {                                                                   \
            __list->__headnode->__next = (__cm_skiplist_node**)__cm_realloc(\
                    __list->__headnode->__next, sizeof(void*) * __level);   \
            __list->__headnode->__prev = (__cm_skiplist_node**)__cm_realloc(\
                    __list->__headnode->__prev, sizeof(void*) * __level);   \
            \
            for(__i = __list->__headnode->__level; __i < __level; __i++)    \
            {                                                               \
                __list->__headnode->__next[__i] = __list->__headnode;       \
                __list->__headnode->__prev[__i] = __list->__headnode;       \
            }                                                               \
            __list->__headnode->__level = __level;                          \
        }                                                                   \
        __node = __list->__headnode;                                        \
        __i = __node->__level - 1;                                          \
        while(__i != -1)                                                    \
        {                                                                   \
            if(__node->__next[__i] == __list->__headnode || cmp(__data, *(type*)(__node->__next[__i] + 1)) < 0) \
            {                                                               \
                if(__i < __level)                                           \
                {                                                           \
                    __newnode->__next[__i] = __node->__next[__i];           \
                    __newnode->__prev[__i] = __node;                        \
                    __newnode->__next[__i]->__prev[__i] = __newnode;        \
                    __newnode->__prev[__i]->__next[__i] = __newnode;        \
                }                                                           \
                __i -= 1;                                                   \
            } else __node = __node->__next[__i];                            \
        }                                                                   \
        __list->__size += 1;                                                \
    } while(0)

#define cm_skiplist_search(list, type, data, cmp, result_node)              \
    do {                                                                    \
        __cm_skiplist* __list = (list);                                     \
        type __data = (data);                                               \
        __cm_skiplist_node* __node;                                         \
        size_t __i;                                                         \
        \
        __node = __list->__headnode;                                        \
        __i = __list->__headnode->__level - 1;                              \
        while(__i != -1)                                                    \
        {                                                                   \
            if(__node->__next[__i] == __list->__headnode || cmp(__data, *(type*)(__node->__next[__i] + 1)) <= 0) \
            {                                                               \
                __i -= 1;                                                   \
            } else __node = __node->__next[__i];                            \
        }                                                                   \
        if(__node->__next[0] != __list->__headnode && cmp(__data, *(type*)(__node->__next[0] + 1)) == 0) \
        {                                                                   \
            (result_node) = __node->__next[0];                              \
        } else {                                                            \
            (result_node) = NULL;                                           \
        }                                                                   \
    } while(0)

#define cm_skiplist_remove(list, node)                                      \
    do {                                                                    \
        __cm_skiplist* __list = (list);                                     \
        __cm_skiplist_node* __node = (node);                                \
        size_t __i;                                                         \
        \
        for(__i = 0; __i < __node->__level; __i++)                          \
        {                                                                   \
            __node->__prev[__i]->__next[__i] = __node->__next[__i];         \
            __node->__next[__i]->__prev[__i] = __node->__prev[__i];         \
        }                                                                   \
        free(__node);                                                       \
        __list->__size -= 1;                                                \
    } while(0)

static __unused __cm_skiplist_node* __cm_skiplist_head_node_sub(__cm_skiplist* list) {
    return list->__size > 0 ? list->__headnode->__next[0] : NULL;
}
static __unused __cm_skiplist_node* __cm_skiplist_tail_node_sub(__cm_skiplist* list) {
    return list->__size > 0 ? list->__headnode->__prev[0] : NULL;
}
static __unused __cm_skiplist_node* __cm_skiplist_next_node_sub(__cm_skiplist* list, __cm_skiplist_node* node) {
    return node->__next[0] != list->__headnode ? node->__next[0] : NULL;
}
static __unused __cm_skiplist_node* __cm_skiplist_prev_node_sub(__cm_skiplist* list, __cm_skiplist_node* node) {
    return node->__prev[0] != list->__headnode ? node->__prev[0] : NULL;
}
#define cm_skiplist_head_node(list)         __cm_skiplist_head_node_sub(list)
#define cm_skiplist_tail_node(list)         __cm_skiplist_tail_node_sub(list)
#define cm_skiplist_next_node(list, node)   __cm_skiplist_next_node_sub(list, node)
#define cm_skiplist_prev_node(list, node)   __cm_skiplist_prev_node_sub(list, node)

static __unused void __cm_skiplist_delmax_sub(__cm_skiplist* list) {
    cm_skiplist_remove(list, list->__headnode->__prev[0]);
}
static __unused void __cm_skiplist_delmin_sub(__cm_skiplist* list) {
    cm_skiplist_remove(list, list->__headnode->__next[0]);
}
#define cm_skiplist_getmax(list, type)      (*(type*)((list)->__headnode->__prev[0] + 1))
#define cm_skiplist_getmin(list, type)      (*(type*)((list)->__headnode->__next[0] + 1))
#define cm_skiplist_delmax(list)            __cm_skiplist_delmax_sub(list)
#define cm_skiplist_delmin(list)            __cm_skiplist_delmin_sub(list)

/* hashmap */
/******************************************************************************/
typedef struct __cm_hashmap_type
{
    struct __cm_vector_struct* __buckets;
    size_t __size;
} __cm_hashmap, *__cm_hashmap_ptr;

#define cm_hashmap_type         __cm_hashmap_ptr
#define cm_hashmap_node_type    __cm_list_node_ptr

#define cm_hashmap_init(hashmap)                                            \
    do {                                                                    \
        __cm_hashmap* __hashmap = (__cm_hashmap*)__cm_malloc(sizeof(__cm_hashmap)); \
        __hashmap->__size = 0;                                              \
        cm_vector_init(__hashmap->__buckets);                               \
        (hashmap) = __hashmap;                                              \
    } while(0)

#define cm_hashmap_destroy(hashmap)                                         \
    do {                                                                    \
        __cm_hashmap* __hashmap = (hashmap);                                \
        size_t __i;                                                         \
        for(__i = 0; __i < cm_vector_size(__hashmap->__buckets); __i++)     \
        {                                                                   \
            cm_list_destroy(cm_vector_data_at(__hashmap->__buckets, __i,  __cm_list*)); \
        }                                                                   \
        cm_vector_destroy(__hashmap->__buckets);                            \
        free(__hashmap);                                                    \
    } while(0)

#define cm_hashmap_node_data(node, type)                                    \
    (*(type*)((char*)((node) + 1) + sizeof(size_t)))

#define cm_hashmap_node_data_ptr(node, type)                                \
    ((type*)((char*)((node) + 1) + sizeof(size_t)))

#define __cm_hashmap_expand(hashmap, type)                                  \
    do {                                                                    \
        cm_mapitem_type_define(__cm_mapitem_type, size_t, type);            \
        __cm_hashmap* __emap = (hashmap);                                   \
        __cm_mapitem_type __eitem;                                          \
        __cm_list* __allnodes;                                              \
        __cm_list* __bucket;                                                \
        __cm_list_node* __node;                                             \
        size_t __hashpos;                                                   \
        size_t __oldsize;                                                   \
        static const size_t __threshold = 8;                                \
        static const size_t __expanding = 1;                                \
        \
        if(__emap->__size >= __threshold * cm_vector_size(__emap->__buckets)) \
        {                                                                   \
            size_t __i;                                                     \
            \
            cm_list_init(__allnodes);                                       \
            for(__i = 0; __i < cm_vector_size(__emap->__buckets); __i++)    \
            {                                                               \
                __bucket = cm_vector_data_at(__emap->__buckets, __i, __cm_list*); \
                cm_list_concatenate(__allnodes, __bucket);                  \
            }                                                               \
            __oldsize = cm_vector_size(__emap->__buckets);                  \
            cm_vector_resize(__emap->__buckets, __emap->__size * __expanding, __cm_list*); \
            \
            for(__i = __oldsize; __i < cm_vector_size(__emap->__buckets);__i++) \
            {                                                               \
                cm_list_init(cm_vector_data_at(__emap->__buckets, __i, __cm_list*)); \
            }                                                               \
            __node = __allnodes->__head->__next;                            \
            while(__node != __allnodes->__head)                             \
            {                                                               \
                __cm_list_node* __nextnode = __node->__next;                \
                \
                __eitem = cm_list_data(__node, __cm_mapitem_type);          \
                __hashpos = __eitem.__key % cm_vector_size(__hashmap->__buckets); \
                \
                __bucket = cm_vector_data_at(__emap->__buckets, __hashpos, __cm_list*); \
                cm_list_insert_node_splice(__bucket, NULL, __node, __allnodes); \
                __node = __nextnode;                                        \
            }                                                               \
            cm_list_destroy(__allnodes);                                    \
        }                                                                   \
    } while(0)

#define cm_hashmap_insert(hashmap, type, data, hash)                        \
    do {                                                                    \
        cm_mapitem_type_define(__cm_mapitem_type, size_t, type);            \
        __cm_hashmap* __hashmap = (hashmap);                                \
        __cm_list* __bucket;                                                \
        __cm_mapitem_type __data_item;                                      \
        type __data = (data);                                               \
        size_t __hashval;                                                   \
        size_t __hashpos;                                                   \
        \
        __hashmap->__size += 1;                                             \
        __cm_hashmap_expand(__hashmap, type);                               \
        \
        __hashval = hash(__data);                                           \
        __hashpos = __hashval % cm_vector_size(__hashmap->__buckets);       \
        __bucket = cm_vector_data_at(__hashmap->__buckets, __hashpos, __cm_list*); \
        \
        __data_item.__key = __hashval;                                      \
        __data_item.__val = __data;                                         \
        cm_list_append(__bucket, __cm_mapitem_type, __data_item);           \
    } while(0)

#define cm_hashmap_search(hashmap, type, data, hash, cmp, result_node)      \
    do {                                                                    \
        cm_mapitem_type_define(__cm_mapitem_type, size_t, type);            \
        __cm_hashmap* __hashmap = (hashmap);                                \
        __cm_list* __bucket;                                                \
        __cm_list_node* __node;                                             \
        __cm_mapitem_type __data_item;                                      \
        type __data = (data);                                               \
        size_t __hashval;                                                   \
        size_t __hashpos;                                                   \
        \
        __hashval = hash(__data);                                           \
        __hashpos = __hashval % cm_vector_size(__hashmap->__buckets);       \
        __bucket = cm_vector_data_at(__hashmap->__buckets, __hashpos, __cm_list*); \
        \
        __node = cm_list_head(__bucket);                                    \
        while(__node)                                                       \
        {                                                                   \
            __data_item = cm_list_data(__node, __cm_mapitem_type);          \
            if(cmp(data, __data_item.__val) == 0)                           \
            {                                                               \
                (result_node) = __node;                                     \
                break;                                                      \
            }                                                               \
            __node = cm_list_next(__bucket, __node);                        \
        }                                                                   \
        (result_node) = __node;                                             \
    } while(0)

#define cm_hashmap_remove(hashmap, node)                                    \
    do {                                                                    \
        __cm_hashmap* __hashmap = (hashmap);                                \
        __cm_list_node* __node = (node);                                    \
        \
        __hashmap->__size -= 1;                                             \
        __node->__prev->__next = __node->__next;                            \
        __node->__next->__prev = __node->__prev;                            \
        cm_free(__node);                                                    \
    } while(0)

static __unused __cm_list_node* __cm_hashmap_head_sub(__cm_hashmap* hashmap)
{
    size_t i = 0;

    while(i < hashmap->__buckets->__size && cm_vector_data_at(hashmap->__buckets, i, __cm_list*)->__size == 0)
        i++;
    if(i < hashmap->__buckets->__size)
        return cm_vector_data_at(hashmap->__buckets, i, __cm_list*)->__head->__next;
    return NULL;
}

static __unused __cm_list_node* __cm_hashmap_next_sub(__cm_hashmap* hashmap, __cm_list_node* node)
{
    cm_mapitem_type_define(cm_mapitem_type, size_t, unsigned char);
    cm_mapitem_type mapitem;
    size_t hashval;
    size_t hashpos;
    cm_list_type bucket;

    mapitem = cm_list_data(node, cm_mapitem_type);
    hashval = mapitem.__key;
    hashpos = hashval % hashmap->__buckets->__size;
    bucket = cm_vector_data_at(hashmap->__buckets, hashpos, cm_list_type);

    if(node->__next != bucket->__head)
        return node->__next;
    else
    {
        hashpos += 1;
        while(hashpos < hashmap->__buckets->__size && cm_vector_data_at(hashmap->__buckets, hashpos, __cm_list*)->__size == 0)
            hashpos += 1;
        if(hashpos < hashmap->__buckets->__size)
            return cm_vector_data_at(hashmap->__buckets, hashpos, __cm_list*)->__head->__next;
    }
    return NULL;
}

#define cm_hashmap_head(hashmap)        __cm_hashmap_head_sub(hashmap)
#define cm_hashmap_next(hashmap, node)  __cm_hashmap_next_sub(hashmap, node)

static __unused size_t __cm_hash_integer(int i)
{
    return i * 299999977 + 200000033;
}
static __unused size_t __cm_hash_string(char* s)
{
    size_t hash = 0;
    size_t i;

    for(i = 0; s[i]; i++)
        hash = __cm_hash_integer(s[i] ^ (hash << 5) ^ (hash >> 27));
    return hash;
}
#define cm_hash_string(x)           __cm_hash_string(x)
#define cm_hash_integer(x)          __cm_hash_integer(x)
#define cm_hash_string_mapitem(x)   __cm_hash_string((x).__key)
#define cm_hash_integer_mapitem(x)  __cm_hash_integer((x).__key)

/* implementation */
/******************************************************************************/
/* any program using cmacro_lib must contain this macro in the source only
 * once because it is not proper to define global variants in header file
 */
#define cm_lib_implementation()                                             \
    size_t __do_not_use_cm_lib_implementation_more_than_once = 0;           \
size_t __cm_thread_safe __cm_jmp_pos = 0;                                   \
jmp_buf __cm_thread_safe __cm_jmp_buf[128]

#endif
/******************************************************************************/
/* EOF */
